rnqoj-57-找啊找啊找GF-二维背包

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
#define INF 99999999  
int dp[101][101];  
int t[101][101];  
int main()  
{  
    int a,b,c,i,j,k,n;  
    while(~scanf("%d",&n))  
    {  
        scanf("%d%d%d",&a,&b,&c);  
        for(j=0;j<101;j++)  
        {  
            for(k=0;k<101;k++)t[j][k]=INF;  
        }  
        dp[0][0]=0;  
        t[0][0]=0;  
        dp[a][b]=1;  
        t[a][b]=c;  
        for(i=2;i<=n;i++)  
        {  
            scanf("%d%d%d",&a,&b,&c);  
            for(j=100;j>=a;j--)  
            {  
                for(k=100;k>=b;k--)  
                {  
                    if(dp[j][k]<dp[j-a][k-b]+1)  
                    {  
                        dp[j][k]=dp[j-a][k-b]+1;  
                        t[j][k]=t[j-a][k-b]+c;  
                    }  
                    if(dp[j][k]==dp[j-a][k-b]+1)  
                    {  
                        t[j][k]=min(t[j-a][k-b]+c,t[j][k]);  
                    }  
                }  
            }  
        }  
        scanf("%d%d",&a,&b);  
        int ts,ns;  
        ns=0;ts=99999;  
        for(i=0;i<=a;i++)  
        {  
            for(j=0;j<=b;j++)  
            {  
                if(dp[i][j]>ns)  
                {  
                    ns=dp[i][j];  
                    ts=t[i][j];  
                }  
                else if(dp[i][j]==ns)  
                {  
                    ts=min(ts,t[i][j]);  
                }  
            }  
        }  
        cout<<ts<<endl;  
    }  
    return 0;  
}