动态规划
本题中的物品涉及两个价值，属于背包问题的简单变形，氧气和氮气各占一维即可。和普通的一维背包问题一样，这里可以通过调整状态转移的顺序来实现空间降维。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <cstdio> #include <cstring> int f[80][80]; int main() { int m,n,a,b,w,num,T; for(scanf("%d",&T);T;--T) { memset(f,-1,sizeof(f)); f[0][0]=0; scanf("%d%d%d",&m,&n,&num); for(int k=0;k<num;++k) { scanf("%d%d%d",&a,&b,&w); for(int i=79;i>=a;--i) for(int j=79;j>=b;--j) if(f[i-a][j-b]>-1&&(f[i][j]==-1||f[i][j]>f[i-a][j-b]+w)) f[i][j]=f[i-a][j-b]+w; } int ans=-1; for(int i=m;i<80;++i) for(int j=n;j<80;++j) if(f[i][j]>-1&&(ans==-1||ans>f[i][j])) ans=f[i][j]; printf("%d\n",ans); } return 0; } |