小明系列故事——买年货

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 110;
 8 int n,v1,v2,k;
 9 int dp[maxn][maxn][10];
10 int a[maxn],b[maxn],val[maxn];
11 
12 int main(){
13     while(~scanf("%d%d%d%d",&n,&v1,&v2,&k)){
14         for( int i=0; i<n; i++ ){
15             cin>>a[i]>>b[i]>>val[i];
16         }
17         int tmp;
18         memset(dp,0,sizeof(dp));
19         for( int i=0; i<n; i++ ){
20             for( int x=v1; x>=0; x-- ){
21                 for( int y=v2; y>=0; y-- ){
22                     for( int j=k; j>=0; j-- ){
23                         tmp=dp[x][y][j];
24                         if(x>=a[i]){
25                             tmp=max(tmp,dp[x-a[i]][y][j]+val[i]);
26                         }
27                         if(y>=b[i]){
28                             tmp=max(tmp,dp[x][y-b[i]][j]+val[i]);
29                         }
30                         if(j>=1){
31                             tmp=max(tmp,dp[x][y][j-1]+val[i]);
32                         }
33                         dp[x][y][j]=max(dp[x][y][j],tmp);
34                         /*cout<<"tmp="<<tmp<<endl;*/
35                     }
36                 }
37             }
38         }
39         cout<<dp[v1][v2][k]<<endl;
40     }
41     return 0;
42 }