zoj3956（01背包）

题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3956

以为01背包会了，稍微变形一下就认不出了。。。。。

将c作为背包体积，h作为价值

背包容量最大为500*100

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long
 5 using namespace std;
 6 int dp[50010];
 7 int main()
 8 {
 9     int n,t;
10     int h,c;
11     scanf("%d",&t);
12     while(t--)
13     {
14         ll ans=0;
15         scanf("%d",&n);
16         memset(dp,0,sizeof(dp));
17         for(int i=0;i<n;i++)
18         {
19             scanf("%d%d",&h,&c);
20             for(int j=100*n;j>=c;j--)
21                 dp[j]=max(dp[j],dp[j-c]+h);
22         }
23         for(int i=0;i<=n*100;i++)
24             ans=max(ans,dp[i]*1ll*dp[i]-dp[i]*1ll*i-i*1ll*i);  //类型转换
25         printf("%lld
",ans);
26     }
27 
28 }