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;}