rqnoj-202-奥运火炬登珠峰 - c++编程基础

一个二维背包问题。

注意两种物品可以带超过当前值。

那么就算出超过的部分的最小值。

若当前已经超过，那么最小值不可能出现在超过后在加一个值，所以当数值已经超过的时候，就不需要算超过的部分的超过了。

#include  
#include  
#include  
#include  
#include  
#define INF 999999999  
using 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<