3维动态规划 hdu 4501 小明系列故事——买年货

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4501

题目大意：

一共有n件商品，每件商品有一个购买价钱，购买积分，得分价值。

现有k件物品的选购机会，有v1元钱，v2积分，问能获得的最大得分价值是多少。

解题思路：

dp[i][j][k]表示有i元钱，j积分和k个免费商品的机会，能获得的最大的得分价值。

对每件商品一共有四种选择，1、用钱买 2、用积分换 3、用一个免费商品的名额 4、什么都不用

代码：

#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;int dp[110][110][10];  //dp[i][j][k]表示有i人民币，j积分,k次免费的机会能够获得的最大价值struct Thing{    int a,b,val;}thing[110];int main(){    int n,v1,v2,k;    while(scanf("%d%d%d%d",&n,&v1,&v2,&k)!=EOF)    {        int sum=0;        for(int i=1;i<=n;i++)        {            scanf("%d%d%d",&thing[i].a,&thing[i].b,&thing[i].val);            sum+=thing[i].val;        }        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++)            for(int q=k;q>=0;q--)            for(int j=v1;j>=0;j--)                for(int p=v2;p>=0;p--)                    {                        if(j>=thing[i].a&&p>=thing[i].b) //如果能够用积分或钱                        {                            dp[j][p][q]=max(max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p-thing[i].b][q]+thing[i].val),dp[j][p][q]);                            if(q>=1)  //如果能用免费的名额                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);                        }                        else if(j<thing[i].a&&p<thing[i].b) //如果钱和积分都不能用                        {                            if(q>=1)                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);                        }                        else if(j<thing[i].a) //只能用积分                        {                            dp[j][p][q]=max(dp[j][p-thing[i].b][q]+thing[i].val,dp[j][p][q]);                            if(q>=1)                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);                        }                        else   //只能用钱                        {                            dp[j][p][q]=max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p][q]);                            if(q>=1)                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);                        }                    }            printf("%d\n",dp[v1][v2][k]);    }    return 0;}