题目大意：
有g种不同颜色的小球，b个袋子，每个袋子里面有若干个每种小球
两人轮流取袋子，当袋子里面的同色小球有s个时，会合并成一个魔法球，并被此次取袋子的人获得
成功获得魔法球的人可以再次取
求二者都进行最优策略之后两人所得魔法球个数差
分析：
博弈，数据很小，自然想到了可以搜索所有状态
然后从每一步的子状态中找到对当前人（这一步的先手）最有利的状态即可
直接搜索还是会超时的，于是想到用状态压缩一下，做记忆化搜索
然后其实就是一个状压dp了
通过某个状态对于先手的最优子状态进行转移。。
代码如下
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
typedef struct Node
{
int a,b;
}node;
node dp[];
bool vi[];
int num[][];
int p[];
int g,b,s,k,m,x;
void dfs(int state,int turn)
{
if(state==(<<b)-)
{
dp[state].a=;
dp[state].b=;
return ;
}
if(vi[state])
{
return ;
}
int ok;
node t;
node ans;
ans.a=-;
ans.b=;
int pp[];
memcpy(pp,p,sizeof(pp));
for(int i=;i<b;i++)
{
t.a=;
t.b=;
ok=;
if(state&(<<i))
continue;
int st=state|(<<i); //状态
for(int j=;j<g;j++)
{
p[j]+=num[i][j];
ok+=p[j]/s;
p[j]%=s;
}
int tur=ok?turn:!turn;//是否交换选手
dfs(st,tur);
memcpy(p,pp,sizeof(pp));
t.a+=ok;
if(tur==turn) //子状态的先手所要转移到的状态相同
{
t.a+=dp[st].a;
t.b+=dp[st].b;
}
else //选手交换了
{
t.b+=dp[st].a;
t.a+=dp[st].b;
}
if(t.a-t.b>ans.a-ans.b)
{
ans=t;
}
}
vi[state]=;
dp[state]=ans;
return ;
}
int main()
{
while(scanf("%d%d%d",&g,&b,&s),g+b+s)
{
memset(num,,sizeof(num));
for(int i=;i<b;i++)
{
scanf("%d",&k);
while(k--)
{
scanf("%d",&x);
num[i][x-]++;
}
}
memset(p,,sizeof(p));
memset(vi,,sizeof(vi));
dfs(,);
printf("%d\n",dp[].a-dp[].b);
}
return ;
}