HDU2697+DP

/*

DP

dp[i][j]: i      cost   j       

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<iostream>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<math.h>

using namespace std;

typedef long long int64;

//typedef __int64 int64;

typedef pair<int64,int64> PII;

#define MP(a,b) make_pair((a),(b)) 

const int maxn = 105;

const int maxm = 10005;

const int inf = 99999099;

const double pi=acos(-1.0);

const double eps = 1e-8;

struct Node{

    int len;

    bool Choosed;

    int maxVal;

}dp[ maxn ][ maxm ];

void init(){

    for( int i=0;i<maxn;i++ ){

        for( int j=0;j<maxm;j++ ){

            dp[i][j].maxVal = 0;

            dp[i][j].len = 0;

            dp[i][j].Choosed = false;

        }

    }

}

int cost[ maxn ];

int main(){

    int T;

    scanf("%d",&T);

    while( T-- ){

        int n,sum;

        scanf("%d%d",&n,&sum);

        //memset( dp,0,sizeof( dp ) );

        init();

        int SumCost = 0;

        int MinCost = inf;

        for( int i=0;i<n;i++ ){

            scanf("%d",&cost[i]);

            SumCost += cost[ i ];

            MinCost = min( MinCost,cost[i] );

        }

        if( MinCost>sum ) {

            printf("0
");

            continue;

        }

        if( MinCost==sum ) {

            printf("1
");

            continue;

        }

        if( sum>=SumCost ){

            printf("%d
",n*n);

            continue;

        }

        

        int ans = 0;

        for( int i=0;i<n;i++ ){

            for( int j=cost[i];j<=sum;j++ ){

                dp[ i ][ j ].maxVal = 1;

                dp[ i ][ j ].len = 1;

                dp[ i ][ j ].Choosed = true;

                ans = 1;

            }

        }//init of dp

        

        for( int i=1;i<n;i++ ){

            for( int j=0;j<=sum;j++ ){

                if( dp[i-1][j].Choosed==false ){

                    if( j>=cost[i] ){

                        if( dp[i-1][j-cost[i]].maxVal+1>=dp[i-1][j].maxVal ){

                            dp[i][j].maxVal = dp[i-1][j-cost[i]].maxVal+1;

                            dp[i][j].len = 1;

                            dp[i][j].Choosed = true;

                        }

                        else {

                            if( dp[i-1][j].maxVal>dp[i][j].maxVal ){

                                dp[i][j].maxVal = dp[i-1][j].maxVal;

                                dp[i][j].len = 0;

                                dp[i][j].Choosed = false;

                            }

                        }

                    }

                    else {

                        if( dp[i-1][j].maxVal>dp[i][j].maxVal ){

                            dp[i][j].maxVal = dp[i-1][j].maxVal;

                            dp[i][j].len = 0;

                            dp[i][j].Choosed = false;

                        }

                    }

                }

                else{

                    if( j>=cost[i] ){

                        if( dp[i-1][j-cost[i]].maxVal-dp[i-1][j-cost[i]].len*dp[i-1][j-cost[i]].len+(dp[i-1][j-cost[i]].len+1)*(dp[i-1][j-cost[i]].len+1)>=dp[i-1][j].maxVal ){

                            dp[i][j].maxVal = dp[i-1][j-cost[i]].maxVal-dp[i-1][j-cost[i]].len*dp[i-1][j-cost[i]].len+(dp[i-1][j-cost[i]].len+1)*(dp[i-1][j-cost[i]].len+1);

                            dp[i][j].len = dp[i-1][j-cost[i]].len+1;

                            dp[i][j].Choosed = true;

                        }

                        else{

                            if( dp[i-1][j].maxVal>dp[i][j].maxVal ){

                                dp[i][j].maxVal = dp[i-1][j].maxVal;

                                dp[i][j].len = 0;

                                dp[i][j].Choosed = false;

                            }

                        }

                    }

                    else{

                        if( dp[i-1][j].maxVal>dp[i][j].maxVal ){

                            dp[i][j].maxVal = dp[i-1][j].maxVal;

                            dp[i][j].len = 0;

                            dp[i][j].Choosed = false;

                        }

                    }

                }

                ans = max(ans,dp[i][j].maxVal);

                //printf("dp[%d][%d].val = %d, len = %d, choose = %d 
",i,j,dp[i][j].maxVal,dp[i][j].len,dp[i][j].Choosed);

            }

        }

        printf("%d
",ans);

    }

    return 0;

}

/*

DP

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<iostream>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<math.h>

using namespace std;

typedef long long int64;

//typedef __int64 int64;

typedef pair<int64,int64> PII;

#define MP(a,b) make_pair((a),(b)) 

const int maxn = 105;

const int inf = 0x7fffffff;

const double pi=acos(-1.0);

const double eps = 1e-8;

int dp[ maxn ][ maxn ];

int a[ maxn ];

int main(){

	int T;

	scanf("%d",&T);

	while( T-- ){

		int n,sum;

		scanf("%d%d",&n,&sum);

		int MinCost = inf;

		for( int i=1;i<=n;i++ ){

			scanf("%d",&a[i]);

			if( a[i]<MinCost ) MinCost = a[i];

		}

		if( MinCost>sum ){

			printf("0
");

			continue;

		}

		if( MinCost==sum ){

			puts("1");

			continue;

		}

		int ans = 0;

		memset( dp,0,sizeof( dp ) );

		for( int i=1;i<=n;i++ ){

			for( int j=0;j<=sum;j++ ){

				int cnt = 0;

				for( int k=1;k<=i;k++ ){

					cnt += a[ i+1-k ];

					if( cnt>j ) break;

					dp[i][j] = max( dp[i][j],dp[i-k][j-cnt]+k*k );

				}

				dp[i][j] = max( dp[i][j],dp[i-1][j] );

				ans = max( ans,dp[i][j] );

			}

		}

		printf("%d
",ans);

	}

	return 0;

}