题目链接：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;

}