【传送门】http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5747
【题目大意】：薛定谔的背包。薛定谔的猫是只有观测了才知道猫的死活，薛定谔的背包是只有把物品放入背包中才知道物品的价值。。有两大类物品，价值分别是k1 , k2,数量分别是n,m，第一大类第i个物品的体积是S(1,i)；第二大类第i个物品的体积是S（2，i）。每件物品被放入背包价值怎么算呢，只有把它放入背包之后才能算出来，该物品对于价值是 k * r;
其中k是物品原本价值，r是放入该物品之后背包的剩余体积。问这个背包所能装入的最大价值是多少？
【题解】背包问题，但又要 先做贪心的处理，为什么可以贪心呢？因为有这样一个事实，对于同一类物品，肯定是优先放体积小的，因为体积小r就大，因此先对两类物品按照体积分别排序。
所以最终选的物品的结果肯定是第一类物品的前i项，第二类物品的前j项 （i,j >= 0）
所以我们可以很轻松地定义DP中的“状态”了。定义dp[i][j]为取了第一类物品的前i项，第二类物品的前j项 所获得的价值。
状态转移方程 ： dp[i][j] = max{ dp[i-1][j] + (C - Sum1[i] - Sum2[j] )*k1 , dp[i][j-1] + (C - Sum2[j] - Sum1[i] )*k1 }
其中Sum1 是第一类物品体积前缀和，Sum2 是第二类物品体积前缀和。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll dp[2020][2020]; ll k1,k2,c; int n,m; ll ans; ll a[2020],b[2020]; ll suma[2020],sumb[2020]; int main(){int t;scanf("%d",&t);while(t--){scanf("%lld%lld%lld",&k1,&k2,&c);scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%lld",&a[i]);}for(int i = 1; i <= m; i++){scanf("%lld",&b[i]);}sort(a+1,a+1+n);sort(b+1,b+1+m);suma[0] = 0;for(int i = 1; i <= n; i++){suma[i] = suma[i-1] + a[i];}sumb[0] = 0;for(int i = 1; i <= m; i++){sumb[i] = sumb[i-1] + b[i];}ans = -1;for(int i = 0; i <= n; i++){for(int j = 0; j <= m; j++){dp[i][j] = 0;if(i == 0 && j == 0) continue;if(i == 0){if(c >= sumb[j]){dp[i][j] = dp[i][j-1] + k2 * (c - sumb[j]);}}else if(j == 0){if(c >= suma[i]){dp[i][j] = dp[i-1][j] + k1 * (c - suma[i]);}}else{ll s = suma[i] + sumb[j];if(c >= s){dp[i][j] = max(dp[i][j-1]+k2*(c-s),dp[i-1][j]+k1*(c-s));}}ans = max(ans,dp[i][j]);}}printf("%lld\n",ans);}return 0; }