ZOJ 3956 Course Selection System （dp 01背包）

思路

题目要求 H2−H∗C−C2 最大，那么就可以认为C尽量小，H尽量大，转换成对于每一个C，求最大的H，因为C的范围只有50000，所以可以直接0-1背包求解

代码

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define rep(i,a,b) for(int i=a;i<b;i++) const int INF=0x3f3f3f3f; const int maxn=1e3+50; const int mod=9901; #define pii pair<int,int> typedef long long ll; typedef unsigned int ui; using namespace std; int w[maxn],c[maxn]; int dp[50050]; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); #endif int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); rep(i,0,n) scanf("%d %d",&w[i],&c[i]); mem(dp,0); rep(i,0,n) for(int j=50000;j>=c[i];j--){ dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } ll ans=0; rep(i,0,50001){ ll totH=dp[i]; ans=max(ans,totH*totH-totH*i-(ll)i*i); } printf("%lld\n",ans); } return 0; }