hdu 4778 Gems Fight（2013 acmicpcアジア地域試合杭州駅I）

http://acm.hdu.edu.cn/showproblem.php?pid=4778
Gems Fight
Time Limit：20000/10000 MS（Java/Others）    メモリLimit：327680/327680 K（Java/Others）Total Submission（s）：355    Acceepted Submission(s)：153
Problem Description
Alice and Bob are playing「Gems Fight！」：
The re are Gems of G different colors，packed in B bags.Each bag has several Gems.G different colors are numberd fromカラー1.
Alice and Bob take turns to pick one bag and collect all the Gems inside.A bag cannot be picked twice.The Gems colleced are stored in a shared cooker.
After a player，we name it as X，put Gems into the cooker，if there re re S Gems which are the sameカラーthe cooker，they will be melted into one Magic Stone.This reation will go and more Magic Store Magic Store Magic Store producedeuntilのS Gems of the sameカラーマイニング.The n X owns those new Magic Stnes.When X gets one or more new Magic Stornes，he/she will also get a bonus turn.If X gets Magic Store.ine a bogaturn，wittern。
The e e will be B turns in total.The goal of“Gems Fight！”is to get as Magic Stornes than the opponent as possible.
Now Alice gets the first turn，and she wants to know，if 
both of the m act the optimal way，what will be the difference between the number of her Magic Stnes and the number of Bob's Magic Stornes the end of the game.
Bの箱の中にG色の宝石が置いてあります。二人は順番に一つの箱を選んで、その中の宝石を一つの鍋に入れます。そして、S個の同じ色の宝石がないと、集まって一つの魔法石になります。そして、今回の得点は魔法石の数です。そして、この輪の誰かが魔法石を手に入れたら、次のラウンドに彼は引き続き箱を選んで宝石に入れることができます。彼はあるラウンドで魔法石を手に入れられなかったことを知っています。今は二人に最適な策略を採用した場合、最後まで持ってきた人の得点と後に取った人の得点の差はいくらですか？
考え方：題意によって、得られた魔法石は一定であることが分かります。つまり、どの順番で選んでも、最後の二人が手にした魔法石の和は一定です。Bは最大21個しかないということが分かります。私たちは記憶化検索でこの問題を解決できます。まずある特定の状態で、鍋に残っている宝石は固定されています。また入手できる魔法石の数も一定です。じゃdp[flags]を設定します。状態はflagsの下で一番多く手に入る魔法石の数を表しています。次は状態転換です。
i番目の箱((flags>>>i)&1==1)を選んだとしたら、どれぐらいの魔法石が得られますか？x個にします。x>0なら、次のラウンドを表しますか？それとも自分で選びますか？
dp[flags]=max(dp[flags]，dp[flags^)（1<次のラウンドは相手の選択です。
ここのleftは現在の状態でいくつの魔法石を持つことができるかを表しています。
最後にdp[(1<コードは以下の通りです

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inf -2100000000
using namespace std;
int dp[1<<21];
int g,b,s;
int box[21][8],c[8];
int dfs(int flag,int left,int cc[])
{
    if(left==0||flag==0)
    return 0;
    if(dp[flag]!=inf)
    return dp[flag];
    int i,tmp,ans=0,ben;
    int tt[8];
    memset(tt,0,sizeof(tt));
    for(i=b-1;i>=0;i--)
    {
        ben=0;
        if((flag>>i)&1)
        {
            tmp=flag^(1<<i);
            int sum=0;
            for(int j=0;j<g;j++)
            {
                tt[j]=(cc[j]+box[i][j]);
                sum+=tt[j]/s;
                tt[j]%=s;
            }
            if(sum)
            {
                ben=sum+dfs(tmp,left-sum,tt);
            }
            else
            {
                ben=left-dfs(tmp,left,tt);
            }
            ans=max(ans,ben);
        }
    }
    return dp[flag]=ans;
}
int main()
{
   // freopen("dd.txt","r",stdin);
    while(scanf("%d%d%d",&g,&b,&s))
    {
        if(!g)
        break;
        memset(box,0,sizeof(box));
        memset(c,0,sizeof(c));
        for(int i=0;i<b;i++)
        {
            int n,x;
            scanf("%d",&n);
            while(n--)
            {
                scanf("%d",&x);
                box[i][x-1]++;
                c[x-1]++;
            }
        }
        int sum=0;
        for(int i=0;i<g;i++)
        {
            sum+=c[i]/s;
        }
        int cc[8];
        int limit=(1<<b);
        for(int i=0;i<limit;i++)
        {
            dp[i]=dp[i]=inf;
        }
        memset(cc,0,sizeof(cc));
        int ans=dfs((1<<b)-1,sum,cc);
        printf("%d
",2*ans-sum);
    }
    return 0;
}