ZOJ 4019 Schrödinger's Knapsack (dp)

落日映苍穹つ 2022-05-27 00:08 85阅读 0赞

[传送门][Link 1]

思路： dp题还是做的太少， 不够灵活，这道题自己第一反应是背包，但容量太大，不可行。按题意分析，每一类里各自的价值是相同，所以当在一类中挑选的时候，当然是体积小的优先。所以对于两类来说也是大趋势是体积小的优先， 所以我们可以从小到大枚举A,B类的任意两个区间， 只要这两个区间的体积和小于总容量就行。但是A,B类的物品顺序还有影响，我们用dp\[i\]\[j\]代表枚举A类的1~i区间，B类的1~j区间。状态转移方程为 dp\[i\]\[j\]=max(dp\[i\]\[j-1\]+vb\*(c-s), dp\[i-1\]\[j\]+va\*(c-s)); 表示我们可以先放A类的第i个物品，或者先放B类的第j个物品，取二者较大值。有一点贪心的感觉在里面

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=2e3+10;
    typedef long long ll;
    
    int T;
    ll dp[maxn][maxn];
    ll va, vb, c, ca[maxn], cb[maxn], suma[maxn], sumb[maxn];
    
    int main(){
    	scanf("%d", &T);
    	
    	while(T--){
    		scanf("%lld%lld%lld", &va, &vb, &c);
    		int  n, m;
    		scanf("%d%d", &n, &m);
    		
    		for(int i=0; i<=n; i++)
    			for(int j=0; j<=m; j++) dp[i][j]=0;//用memset初始化会T；
    		
    		for(int i=1; i<=n; i++)
    			scanf("%lld", &ca[i]);	
    		for(int i=1; i<=m; i++)
    			scanf("%lld", &cb[i]);
    		
    		sort(ca+1, ca+1+n); sort(cb+1, cb+1+m);
    		for(int i=1; i<=n; i++)
    			suma[i]=suma[i-1]+ca[i];
    		for(int i=1; i<=m; i++)
    			sumb[i]=sumb[i-1]+cb[i];
    		
    		ll ans=0;
    		for(int i=1; i<=n; i++)
    			if(suma[i]<=c){
    				 dp[i][0]=va*(c-suma[i])+dp[i-1][0];
    				 ans=max(ans, dp[i][0]);	
    			}
    		for(int j=1; j<=m; j++)
    			if(sumb[j]<=c){
    				dp[0][j]=vb*(c-sumb[j])+dp[0][j-1];
    				ans=max(ans, dp[0][j]);	
    			} 
    		
    		
    		for(int i=1; i<=n; i++)
    			for(int j=1; j<=m; j++)
    			{
    				ll s=suma[i]+sumb[j];
    				if(s<=c)
    				{
    					dp[i][j]=max(dp[i-1][j]+va*(c-s), dp[i][j-1]+vb*(c-s));
    					ans=max(ans, dp[i][j]);
    				}
    			}
    		printf("%lld\n", ans);
    	}
    	
    	
    	return 0;
    }

[Link 1]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5747