鉴于G宝石，B包。和S。S当代表凑齐每种颜色的宝石S我们可以成为哲学家的石头

每个软件包包含N宝石。分别c1，c2.......

然后他们轮流拿包。每个包可以得到一次。宝石出包放在地上。

假设你可以成为魔法石拿着魔法石，次还这个人拿包。没变成则换人。

魔法石的个数就是获得分数，问两人最优的时候分差是多少。

状压记忆化搜索

一共21个包。状压存当前取包的状态

不管如何取，最后获得的魔法石数量一定

dp[i]表示在i状态下。先手能够获得的最高分数

#include "stdio.h"

#include "string.h"

int aim,g,b,s;

int dp[1<<22],c[25][10];

int bit[25];

int inf=0x3f3f3f3f;

int Max(int a,int b)

{

    if (a<b)return b;

    else return a;

}

int dfs(int cur,int sum,int temp[])

{

    int ans,i,next,j,w,cnt;

    int mark[10];

    if (cur==aim || sum==0) return 0;

    if (dp[cur]!=inf) return dp[cur];

    ans=0;

    for (i=1;i<=b;i++)

        if (cur&bit[i])

        {

            next=cur^bit[i];

            cnt=0;

            for (j=1;j<=g;j++)

            {

                mark[j]=temp[j]+c[i][j];

                cnt+=mark[j]/s;

                mark[j]%=s;

            }

            if (cnt>0) w=cnt+dfs(next,sum-cnt,mark);

            else w=sum-dfs(next,sum,mark);

            ans=Max(ans,w);

        }

    return dp[cur]=ans;

}

int main()

{

    int i,n,x,sum,aim,ans;

    int all[10],mark[25];

    bit[1]=1;

    for (i=2;i<=22;i++)

        bit[i]=bit[i-1]*2;

    while (scanf("%d%d%d",&g,&b,&s)!=EOF)

    {

        if (g+b+s==0) break;

        memset(c,0,sizeof(c));

        memset(all,0,sizeof(all));

        for (i=1;i<=b;i++)

        {

            scanf("%d",&n);

            while (n--)

            {

                scanf("%d",&x);

                c[i][x]++;

                all[x]++;

            }

        }

        sum=0;

        for (i=1;i<=g;i++)

            sum+=all[i]/s;

        aim=bit[b+1]-1;

        memset(mark,0,sizeof(mark));

        memset(dp,inf,sizeof(dp));

        ans=dfs(0,0,mark);

        printf("%d\n",ans-(sum-ans));

    }

    return 0;

}