题意
有n种课可供选择，每一种课有一个H值(1<=H<=10000)和C值(1<=C<=100)，每种课只能选一次。现要求选一些课使得下式的值最大：
[(sum^m_{i=1}H_{x_i})^2-(sum^m_{i=1}H_{x_i}) imes (sum^m_{i=1}C_{x_i})-(sum^m_{i=1}C_{x_i})^2
]
求这个最大值
分析
观察这个式子，首先ΣH的和必须要比ΣC大，不然该式恒为负。然后将ΣC固定为常数，该式变为关于ΣH的二次函数，而又ΣH>ΣC，ΣH在对称轴右边，所以对于一个固定的ΣC，ΣH越大越好。题目中C很小，ΣC也就5e4，可以记录下来，那么本题也就是以ΣC为体积的0-1背包
AC代码
//ZOJ-3956 Course Selection System
//AC 2017-4-10 18:08:51
//DP, 0-1 backpack
#include <bits/stdc++.h>
using namespace std;
const int maxn=600;
const int maxm=105*maxn;
int T,n;
int h,c;
int dp[maxm];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(dp,0,sizeof dp);
for(int i=1;i<=n;++i)
{
scanf("%d %d",&h,&c);
//if(h<c) continue;
for(int j=n*100;j>=c;--j)
dp[j]=max(dp[j],dp[j-c]+h);
}
long long res=0;
for(int i=0;i<=n*100;++i)
res=max(res,dp[i]*1LL*dp[i]-dp[i]*1LL*i-i*1LL*i);
cout<<res<<endl;
}
return 0;
}