【传送门】
【题目大意】：薛定谔的背包。薛定谔的猫是只有观测了才知道猫的死活，薛定谔的背包是只有把物品放入背包中才知道物品的价值。。有两大类物品，价值分别是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#include #include #include 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;}