HDU OJ 4501 小明系列故事——買年貨

思路：三維~~~~~

AC代碼：

[cpp]
#include<stdio.h>  
#include<stdlib.h>  
#include<iostream>  
#include<cstring>  
#include<algorithm>  
 
using namespace std; 
const int Max = 100 +10; 
const int base = 2; 
const int inf = -0x7fffffff; 
int dp[Max][Max][10]; 
struct Monster 
{ 
    int a; 
    int b; 
    int w; 
}g[Max]; 
int dp_find(int n,int v1,int v2,int k) 
{ 
    int x,y,i,j; 
    memset(dp,0,sizeof(dp)); 
    for(x = 0 ;x < n;x ++) 
    { 
        for(y = v1; y >= 0;y --) 
        { 
            for(i = v2;i >= 0;i --) 
            { 
                for(j = k;j >= 0 ;j --) 
                { 
                    int temp = dp[y][i][j]; 
                    if(y>=g[x].a) 
                        temp = max(temp,dp[y-g[x].a][i][j] + g[x].w); 
 
                    if(i>=g[x].b) 
                        temp = max(temp,dp[y][i-g[x].b][j] + g[x].w); 
 
                    if(j>=1) 
                        temp = max(temp,dp[y][i][j-1] + g[x].w); 
 
                    dp[y][i][j] = max(dp[y][i][j],temp); 
                } 
            } 
        } 
    } 
    return dp[v1][v2][k]; 
} 
int main() 
{ 
    int i,j,n,m,k,v1,v2; 
    while(~scanf("%d%d%d%d",&n,&v1,&v2,&k)) 
    { 
        for(i = 0;i < n;i ++) 
            scanf("%d%d%d",&g[i].a,&g[i].b,&g[i].w); 
        //puts("find is begging\n");  
        printf("%d\n",dp_find(n,v1,v2,k)); 
    } 
} 

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int Max = 100 +10;
const int base = 2;
const int inf = -0x7fffffff;
int dp[Max][Max][10];
struct Monster
{
    int a;
    int b;
    int w;
}g[Max];
int dp_find(int n,int v1,int v2,int k)
{
    int x,y,i,j;
    memset(dp,0,sizeof(dp));
    for(x = 0 ;x < n;x ++)
    {
        for(y = v1; y >= 0;y --)
        {
            for(i = v2;i >= 0;i --)
            {
                for(j = k;j >= 0 ;j --)
                {
                    int temp = dp[y][i][j];
                    if(y>=g[x].a)
                        temp = max(temp,dp[y-g[x].a][i][j] + g[x].w);

                    if(i>=g[x].b)
                        temp = max(temp,dp[y][i-g[x].b][j] + g[x].w);

                    if(j>=1)
                        temp = max(temp,dp[y][i][j-1] + g[x].w);

                    dp[y][i][j] = max(dp[y][i][j],temp);
                }
            }
        }
    }
    return dp[v1][v2][k];
}
int main()
{
    int i,j,n,m,k,v1,v2;
    while(~scanf("%d%d%d%d",&n,&v1,&v2,&k))
    {
        for(i = 0;i < n;i ++)
            scanf("%d%d%d",&g[i].a,&g[i].b,&g[i].w);
        //puts("find is begging\n");
        printf("%d\n",dp_find(n,v1,v2,k));
    }
}