Gems Fight

原题：Gems Fight

原题大意

有 G 种颜色的宝石，放在 B 个袋子里（每种颜色可以放多个）。
两人轮流选袋子（每个袋子只能被选 1 次），每次将选出来的袋子中的宝石放到 cooker 中，cooker 可能会起反应。
反应条件是 cooker 中出现 S 个一样颜色的宝石，而且一旦起反应，每 S 个一样颜色的宝石就会获得 1 个魔法石（同时反应）。
作为奖励，每次反应结束后当前玩家可以再选一个袋子继续游戏。
游戏目标是自己获得的魔法石尽量多，双方都采取最优策略的情况下，问最终两个玩家的魔法石之差。

算法分析

数据范围很小，毫不犹豫地状压。
dp[S]：集合S被取走，此景此境，先手最多能赢后手多少分。
遍历不在集合中的袋子，如果拿了i号袋子后不能合成魔法石，
那么dp[S] = max(dp[S], -dp[S|1 << i]), 否则就可以连
任dp[S] = max(dp[S], dp[S|1 << i] + 拿i号袋子获得的收益。

程序代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1e8+7;
int dp[1<<21], res[1<<21][10];
int cnt[21][10], vis[1<<21];
int b, g, n, s, c;


int dfs(int S){
    if(dp[S] != -INF) return dp[S];
    if(S == ((1<<b) - 1)) return dp[S] = 0;
    for(int i = 0; i < b; i++){
        if(!((1<<i)&S)){
            int val = 0;
            for(int j = 1; j <= g; j++)
                val += (res[S][j] + cnt[i][j]) / s;
            if(val > 0)
                dp[S] = max(dp[S], val + dfs(S+(1<<i)));
            else
                dp[S] = max(dp[S], val - dfs(S+(1<<i)));
        }
    }
    return dp[S];
}


void dfs1(int x){
    if(vis[x]) return;
    vis[x] = 1;
    for(int i = 0; i < b; i++){
        if(!(x&(1<<i)))
        {
            for(int j = 1; j <= g; j++)
            {
                res[x+(1<<i)][j] = (res[x][j] + cnt[i][j]) % s;
            }
            dfs1(x+(1<<i));
        }
    }
}


int main(){
    while(~scanf("%d %d %d", &g, &b, &s) && (b+g+s)){
        for(int i = 0; i < (1<<b); i++)
        {
            vis[i] = 0;
            dp[i] = -INF;
            for(int j = 0; j <= g; j++)
                res[i][j] = 0;
        }
        for(int i = 0; i < b; i++)
            for(int j = 0; j<=g; j++)
                cnt[i][j] = 0;
        for(int i = 0; i < b; i++)
        {
            scanf("%d", &n);
            for(int j = 1; j <= n; j++)
            {
                scanf("%d", &c);
                cnt[i][c]++;
            }
        }
        dfs1(0);dfs(0);
        printf("%d\n", dp[0]);
    }
    return 0;
}