题解原文

这题完全不会。。看了题解好像似懂非懂。。。先把题解弄这里来，慢慢研究

题意：

GG有两张奖券，面额分别为V1、V2，准备给MM买礼物。当天是MM生日，所以MM

还可以免费得到一份礼物。

礼物有价格和幸福值两个参数，并且礼物分为特殊礼物和普通礼物，特殊礼物

是一定要全部到手的。

两张奖券不可以合并使用，一种礼物也只能买一次。

问MM最大幸福值是多少，如果特殊礼物不能全部得到MM会不高兴，幸福值为-1 。

分析：这是一个二重01背包，因为还有免费的礼物，故还要增加一维

用f[v1][v2][s]表示奖券V1,V2分别使用v1,v2时，且状态为s时候(s=1表示已经免费得到一份礼物了，s=0表示还木有免费得到礼物)，

MM的幸福值。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define MAXN 505using namespace std;struct node{    int cost,h;}sp[MAXN],norm[MAXN];int numsp,numnorm;int f[MAXN][MAXN][2];int V1,V2,n;bool getSpecial(){    memset(f,-1,sizeof(f));    f[0][0][0]=0;    int pre=0,total=0;    for(int i=0;i
          
           =0;j--)    for(int k=V2;k>=0;k--){        if(f[j][k][1]==pre){            if(j+sp[i].cost<=V1){                f[j+sp[i].cost][k][1]=total;            }            if(k+sp[i].cost<=V2)f[j][k+sp[i].cost][1]=total;        }        if(f[j][k][0]==pre){            if(j+sp[i].cost<=V1){                f[j+sp[i].cost][k][0]=total;            }            if(k+sp[i].cost<=V2)f[j][k+sp[i].cost][0]=total;            f[j][k][1]=total;        }    }    }    bool flag=false;    for(int i=V1;i>=0;i--)    for(int j=V2;j>=0;j--)    for(int s=0;s<=1;s++){        if(f[i][j][s]==total)flag=true;        else f[i][j][s]=-1;    }    return flag;}int getnorm(){    for(int i=0;i
           
            =0;j--) for(int k=V2;k>=0;k--){ for(int s=0;s<=1;s++){ if(f[j][k][s]!=-1){ if(j+norm[i].cost<=V1&&f[j][k][s]+norm[i].h>f[j+norm[i].cost][k][s]) f[j+norm[i].cost][k][s]=f[j][k][s]+norm[i].h; if(k+norm[i].cost<=V2&&f[j][k][s]+norm[i].h>f[j][k+norm[i].cost][s]) f[j][k+norm[i].cost][s]=f[j][k][s]+norm[i].h; } } if(f[j][k][0]!=-1&&f[j][k][0]+norm[i].h>f[j][k][1]) f[j][k][1]=f[j][k][0]+norm[i].h; } } int ans=0; for(int i=V1;i>=0;i--) for(int j=V2;j>=0;j--) for(int s=0;s<=1;s++) ans=max(ans,f[i][j][s]); return ans;}int main(){ freopen("in.txt","r",stdin); int cas=1; while(scanf("%d%d%d",&V1,&V2,&n)==3){ if(V1==0&&V2==0&&n==0)break; int a,b,c; numsp=0,numnorm=0; for(int i=0;i