rqnoj-202-奥运火炬登珠峰
一个二维背包问题。
注意两种物品可以带超过当前值。
那么就算出超过的部分的最小值。
若当前已经超过，那么最小值不可能出现在超过后在加一个值，所以当数值已经超过的时候，就不需要算超过的部分的超过了。
#include<string.h>#include<stdio.h>#include<iostream>#include<algorithm>#include<math.h>#define INF 999999999using namespace std;int dp[101][101];int main(){ int t,a,n; int i,j,x,y,z; while(~scanf("%d%d",&t,&a)) { for(i=0;i<101;i++) { for(j=0;j<101;j++) { dp[i][j]=INF; } } dp[0][0]=0; int fa,fb; fa=fb=0; scanf("%d",&n); while(n--) { scanf("%d%d%d",&x,&y,&z); for(i=fa;i>=0;i--) { for(j=fb;j>=0;j--) { if(i+x<101&&j+y<101)dp[i+x][j+y]=min(dp[i][j]+z,dp[i+x][j+y]); } } if(fa+x<101)fa=fa+x; if(fb+y<101)fb=fb+y; } int MIN; MIN=INF; for(i=t;i<=fa;i++) { for(j=a;j<=fb;j++) { MIN=min(MIN,dp[i][j]); } } cout<<MIN<<endl; } return 0;}