Hdu 4778 Gems Fight! (状态压缩 + DP)

题目链接：

题目描述：

　　就是有G种颜色，B个背包，每个背包有n个宝石，颜色分别为c1，c2...........。两个人轮流取背包放到公共容器里面，容器里面有s个相同颜色宝石的时候，这s个相同颜色的宝石会融合成一个魔法石。当选手选择一个背包放到公共容器里会产生魔法石，魔法石就归这个选手所有，并且奖励这个选手再选一个背包，直到不再产生魔法石为止。(每个背包只能选取一次)每个选手会尽量使自己得到的魔法石最多，问最后先手减后手的值？

解题思路：

　　数据范围比较小，很容易想到状态压缩。然后就是状态压缩的姿势了。考虑到最后产生的魔法石数目是一定的，只不过是选择的策略不同先手和后手拿到的魔法石数目会不同。所以我们可以枚举第一个选中的背包。dp[i] 表示状态i的最优解(先手-后手得分的最大值)。枚举第j个背包是最后加入的，如果第j个加入不能产生魔法石，那么就要 - dp[i^(1<<j)]，因为加入不能产生魔法石，以前的第一个背包要让给后手选，那么第j个背包加入会产生魔法石，那么就 + dp[1^(1<<j)]，这样原来第一个背包还是作为奖励让前手选。

 1 #include<stdio.h>
 2 #include <queue>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<stdlib.h>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 typedef long long LL;
10 const int maxn = 22;
11 const int INF = 0x3f3f3f3f;
12 int dp[1<<maxn], c[maxn][10], a[maxn], b[maxn];
13 
14 int main ()
15 {
16     int G, B, S;
17     while (scanf ("%d %d %d", &G, &B, &S), G + B + S)
18     {
19         int num, x;
20         memset (c, 0, sizeof(c));
21         for (int i=0; i<B; i++)
22         {
23             scanf ("%d", &num);
24             for (int j=0; j<num; j++)
25             {
26                 scanf ("%d", &x);
27                 c[i][x] ++;
28             }
29         }
30 
31         dp[0] = 0;
32         int n = 1 << B;
33         for (int i=1; i<n; i++)
34         {
35             dp[i] = -INF;
36             memset (a, 0, sizeof(a));
37             for (int j=0; j<B; j++)
38             {
39                 if ((i & (1<<j)) == 0)
40                 {
41                     for (int k=1; k<=G; k++)
42                         a[k] += c[j][k];
43                 }
44             }
45             
46             for (int j=0; j<B; j++)
47                 a[j] %= S;
48                 
49             for (int j=0; j<B; j++)
50             {
51                 if ((i & (1<<j)))
52                 {
53                     int nu = 0;
54                     for (int k=1; k<=G; k++)
55                         nu += (a[k] + c[j][k]) / S;
56                         
57                     if (nu)
58                         dp[i] = max (dp[i], nu + dp[i^(1<<j)]);
59                     else
60                         dp[i] = max (dp[i], nu - dp[i^(1<<j)]);
61                 }
62             }
63         }
64         printf ("%d
", dp[n-1]);
65     }
66     return 0;
67 }

Hdu 4778 Gems Fight! (状态压缩 + DP)

相关推荐