题意：
有n个数，每个数都有价钱，连续的取可以获得len*len的利益，使利益最大。
思路：
三维DP，1、2、3维分别是第i个，剩余多少钱，从后往前连续的有几个。
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\Users\13606\Desktop\Input.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr strcat 13 #include <string> 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 #include <cassert> 21 #include <iomanip> 22 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 23 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 24 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 25 //****************** 26 clock_t __STRAT,__END; 27 double __TOTALTIME; 28 void _MS(){__STRAT=clock();} 29 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;} 30 //*********************** 31 #define rint register int 32 #define fo(a,b,c) for(rint a=b;a<=c;++a) 33 #define fr(a,b,c) for(rint a=b;a>=c;--a) 34 #define mem(a,b) memset(a,b,sizeof(a)) 35 #define pr printf 36 #define sc scanf 37 #define ls rt<<1 38 #define rs rt<<1|1 39 typedef pair<int,int> PII; 40 typedef vector<int> VI; 41 typedef long long ll; 42 const double E=2.718281828; 43 const double PI=acos(-1.0); 44 const ll INF=(1LL<<60); 45 const int inf=(1<<30); 46 const double ESP=1e-9; 47 const int mod=(int)1e9+7; 48 const int N=(int)1e2+10; 49 50 int a[N]; 51 int dp[N][N][N]; 52 53 void solve() 54 { 55 int n,m; 56 sc("%d%d",&n,&m); 57 for(int i=1;i<=n;++i) 58 sc("%d",&a[i]); 59 for(int i=0;i<=n;++i) 60 for(int j=0;j<=m;++j) 61 for(int k=0;k<=n;++k) 62 dp[i][j][k]=-inf; 63 dp[0][m][0]=0; 64 for(int i=1;i<=n;++i) 65 { 66 for(int j=0;j<=m;++j) 67 { 68 for(int k=0;k<=i;++k) 69 dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k]); 70 if(j+a[i]<=m) 71 for(int k=1;k<=i;++k) 72 { 73 // if(dp[i-1][j+a[i]][k-1]!=-inf)都可以or取max; 74 dp[i][j][k]=max(dp[i][j][k],dp[i-1][j+a[i]][k-1]+2*k-1); 75 } 76 } 77 /* for(int j=0;j<=m;++j) 78 for(int k=0;k<=n;++k) 79 pr("%3d%c",dp[i][j][k]," "[k==n]); 80 pr("------------------------------------------- ");*/ 81 } 82 int ans=0; 83 for(int j=0;j<=m;++j) 84 for(int k=0;k<=n;++k) 85 ans=max(ans,dp[n][j][k]); 86 pr("%d ",ans); 87 } 88 89 int main() 90 { 91 int T; 92 sc("%d",&T); 93 while(T--)solve(); 94 return 0; 95 } 96 97 /**************************************************************************************/