首页 > 代码库 > [博弈dp] hdu 4778 Gems Fight

[博弈dp] hdu 4778 Gems Fight

给出g种颜色的宝石,然后有B个背包,S代表到时候每种颜色的宝石凑齐S个能变成一个魔法石
然后B行数输入,每个包里有哪些宝石
然后A,B轮流拿包,每个包只能拿一次,拿出包把宝石放地上。
如果能变成魔法石则拿走魔法石,下一次还这个人拿包,没变成则换人。
魔法石的个数就是获得分数,问两人最优的时候分差是多少。
思路:
只有21个包,状压dp。
然后发现不管顺序如何 最后构成的魔法石的个数是一定的。
然后在不同的二进制状态下,所剩在地面上的宝石是一定的。
那么就可以dp[i] 代表i这个状态下 先手取所获得的最多得分。
dp[(1<<B)-1] 则是先手的答案了
然后已知构成魔法石数sum
则答案就是  dp[(1<<B)-1]-(sum-dp[(1<<B)-1])
每次只要枚举取拿个包 然后保留最大值

代码:

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
    1. #include"cstdlib"  
    2. #include"cstdio"  
    3. #include"cstring"  
    4. #include"cmath"  
    5. #include"queue"  
    6. #include"algorithm"  
    7. #include"iostream"  
    8. #define inf 99999999  
    9. using namespace std;  
    10. int bag[22][12],c[12];  
    11. int dp[1<<22];  
    12. int g,n,s;  
    13. int dfs(int x,int sum,int used[])  
    14. {  
    15.     if(x==0||sum==0) return 0;  
    16.     if(dp[x]!=inf) return dp[x];  
    17.     int ans=0,mark[12];  
    18.     memset(mark,0,sizeof(mark));  
    19.     for(int i=0; i<n; i++)  
    20.     {  
    21.         int pp=0;  
    22.         if(x&(1<<i))  
    23.         {  
    24.             int tep=x^(1<<i),cnt=0;  
    25.             for(int j=0; j<g; j++)  
    26.             {  
    27.                 mark[j]=used[j]+bag[i][j];  
    28.                 cnt+=mark[j]/s;  
    29.                 mark[j]%=s;  
    30.             }  
    31.             if(cnt>0) pp=cnt+dfs(tep,sum-cnt,mark);  //构成魔法石继续取  
    32.             else pp=sum-dfs(tep,sum,mark);         //换人了  得到的就是别人剩下的  
    33.             ans=max(ans,pp);  
    34.         }  
    35.   
    36.     }  
    37.     return dp[x]=ans;  
    38. }  
    39. int main()  
    40. {  
    41.     while(scanf("%d%d%d",&g,&n,&s),(g+n+s))  
    42.     {  
    43.         memset(bag,0,sizeof(bag));  
    44.         memset(c,0,sizeof(c));  
    45.         for(int i=0; i<n; i++)  
    46.         {  
    47.             int x;  
    48.             scanf("%d",&x);  
    49.             while(x--)  
    50.             {  
    51.                 int y;  
    52.                 scanf("%d",&y);  
    53.                 bag[i][y-1]++;  
    54.                 c[y-1]++;  
    55.             }  
    56.         }  
    57.         int sum=0;  
    58.         for(int i=0; i<g; i++) sum+=c[i]/s;  //统计能构成多少个魔法石  
    59.         for(int i=0; i<(1<<n); i++) dp[i]=inf;  
    60.         int used[12];  
    61.         memset(used,0,sizeof(used));  
    62.         int ans=dfs((1<<n)-1,sum,used);  
    63.         printf("%d\n",ans-(sum-ans));  
    64.     }  
    65.     return 0;  

[博弈dp] hdu 4778 Gems Fight