首页 > 代码库 > hdu 4778 Rabbit Kingdom(状态压缩)

hdu 4778 Rabbit Kingdom(状态压缩)

题目链接:hdu 4778 Rabbit Kingdom

题目大意:Alice和Bob玩游戏,有一个炉子,可以将S个相同颜色的宝石换成一个魔法石,现在有B个包,每个包里有若干个宝石,给出宝石的颜色。现在由Alice开始,两人轮流选取一个包的宝石放入炉中,每当获得一个魔法石时,可以额外获得一次机会再选一个包放入。两人均按照自己的最优策略,问说最后Alice的魔法石-Bob的魔法石是多少。

解题思路:状态压缩,221,对于每次移动到下一个状态,如果获得的魔法石g非零,则说明下一个状态还是自己在取,则要选择最优的。如果g为0,则说明下一个状态不是自己在取,则要取尽量小的,对应也就是相反数尽量大的。

C++ 记忆化版
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxb = 21; const int maxn = 1<<21; const int maxg = 10; const int INF = 0x3f3f3f3f; int G, B, S; int c[maxb+5][maxg], s[maxn+5][maxg]; int v[maxn+5], dp[maxn+5]; void init () { int t, a; memset(c, 0, sizeof(c)); memset(v, 0, sizeof(v)); for (int i = 0; i < B; i++) { scanf("%d", &t); for (int j = 0; j < t; j++) { scanf("%d", &a); c[i][a]++; } } for (int i = 0; i < (1<<B); i++) { for (int j = 0; j < B; j++) { if (i&(1<<j)) continue; int e = i|(1<<j); if (v[e]) continue; for (int k = 1; k <= G; k++) s[e][k] = (s[i][k] + c[j][k]) % S; } } } int add (int k, int x) { int ans = 0; for (int i = 1; i <= G; i++) ans += (s[k][i] + c[x][i]) / S; return ans; } int dfs (int u) { if (u + 1 == (1<<B)) return 0; if (v[u]) return dp[u]; int up = -INF; int lower = INF; for (int i = 0; i < B; i++) { if (u&(1<<i)) continue; int g = add (u, i); if (g) up = max(up, dfs(u|(1<<i))+g); else lower = min(lower, dfs(u|1<<i)); } v[u] = 1; return dp[u] = max(up, -lower); } int main () { while (scanf("%d%d%d", &G, &B, &S) == 3 && G + B + S) { init(); memset(v, 0, sizeof(v)); printf("%d\n", dfs(0)); } return 0; }
C++ 递推版
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxb = 21; const int maxn = 1<<21; const int maxg = 10; const int INF = 0x3f3f3f3f; int G, B, S; int c[maxb+5][maxg], s[maxn+5][maxg]; int v[maxn+5], dp[maxn+5]; void init () { int t, a; memset(c, 0, sizeof(c)); memset(v, 0, sizeof(v)); for (int i = 0; i < B; i++) { scanf("%d", &t); for (int j = 0; j < t; j++) { scanf("%d", &a); c[i][a]++; } } for (int i = 0; i < (1<<B); i++) { for (int j = 0; j < B; j++) { if (i&(1<<j)) continue; int e = i|(1<<j); if (v[e]) continue; for (int k = 1; k <= G; k++) s[e][k] = (s[i][k] + c[j][k]) % S; } } } int add (int k, int x) { int ans = 0; for (int i = 1; i <= G; i++) ans += (s[k][i] + c[x][i]) / S; return ans; } int solve () { int e = (1<<B) - 1; memset(dp, -INF, sizeof(dp)); dp[e] = 0; for (int u = e; u >= 0; u--) { for (int i = 0; i < B; i++) { if ((u&(1<<i)) == 0) continue; int ui = u-(1<<i); int g = add(ui, i); if (g) dp[ui] = max(dp[ui], dp[u] + g); else dp[ui] = max(dp[ui], -dp[u]); } } return dp[0]; } int main () { while (scanf("%d%d%d", &G, &B, &S) == 3 && G + B + S) { init(); printf("%d\n", solve()); } return 0; }