这一题特别像大白书Ch1的 ex.28 Sum游戏，臣妾对着这个example+看了一堆题解终于把这道博弈DP想清楚了%>_<%
首先要注意这一题里面总的score是不变的，因为bag都放在同一个cooker里，magic stone要么给A要么给B
用二进制数表示当前状态，1001表示A or B有第一个和第四个bag可以选，第二个和第三个bag之前已经选过了（即不可选）所以对应的score[1001]应该计算把第二个和第三个bag放到cooker可以得到的score，我开始把这个弄反了==算成了第一个和第四个的score==
dp[state]表示当前状态（有哪些bag可选，有哪些bag已经选过了）开始博弈，到最后先手得分的最大值。
状态转移时，假设state对应的是A是先手，如果state&(1<<i）!=0，则说明bag i可选，下一个状态就是newstate=state^(1<<i），newstate其实就是将state里面的i位从1变到0，表示已经选过了bag i。
改变的分数就是val=score[newstate]-score[state]
如果val>0，那么下一步还是A，所以dp[state]=max(dp[state],val+dp[newstate])
如果选bag i无法使得A加分，那么下一步就换成B是先手，所以dp[newstate]就表示B是先手，选到最后，B得分最大值，因为总分数一定的，所以A的分数=state状态下对应的总分数-dp[下一个回合B先出手]
state状态下对应的总分数=score[0]-score[state]，假设state=1001，那么现在还可以把bag 1 and bag 4放进去，而score[1001]表示把bag 2 和bag 3 放进cooker的得分，所以要用total score相减
因为一直取max，就可以保证是最优的。
这里面状态转移不会转移到非法的状态，所以记忆化搜索里面也木有非法状态的特判。
最后的分数=dp[(1<<b)-1]-(score[0]-dp[(1<<b)-1])，score[0]表示total score
DP过程中先手后手对应的是A还是B是会变的==
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
using namespace std;
//hdu 4778
const int maxn=1<<21;
int b;
int g;
int n;
int s;
int c[22][12];
int score[maxn];
int sum[20];
int dp[maxn];
int vis[maxn];
void caltotal()//计算cooker中每个状态的score，=0表示已经选过了放进了cooker
{
for(int m=0;m<(1<<b);m++)
{
memset(sum,0,sizeof(sum));
for(int i=0;i<b;i++)
{
if((m&(1<<i))==0)
{
for(int j=1;j<=g;j++)
{
sum[j]+=c[i][j];
}
}
}
for(int i=1;i<=g;i++)
{
score[m]+=sum[i]/s;
}
}
}
int dfs(int state)
{
if(vis[state])
{
return dp[state];
}
vis[state]=1;
int ret=0;
for(int i=0;i<b;i++)
{
if(state&(1<<i))//=1表示当前状态已经存在bag i，所以i可选。向选过bag i的状态转移（所以newstate的i位是0）
{
int newstate=state^(1<<i);
int val=score[newstate]-score[state];
if(val>0)
{
ret=max(ret,val+dfs(newstate));
}
else
{
ret=max(ret,(score[0]-score[state])-dfs(newstate));
//所有bag都放到cooker中的score-当前状态还有某些包可选对应的score（只放了一部分bag到cooker里的score）=s当前状态的总分数
}
}
}
return dp[state]=ret;//一定要赋值才能实现记忆化搜索！
}
int main()
{
freopen("input.txt","r",stdin);
//freopen("data.txt","r",stdin);
//freopen("out1.txt","w",stdout);
while(true)
//while(scanf("%d %d %d",&g,&b,&s),g|b|s)
{
scanf("%d %d %d",&g,&b,&s);
if(!b&&!g&&!s) break;
memset(score,0,sizeof(score));
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
for(int i=0;i<b;i++)
{
scanf("%d",&n);
for(int j=0;j<n;j++)
{
int color=0;
scanf("%d",&color);
c[i][color]++;
}
}
caltotal();
int ans=dfs((1<<b)-1)*2-score[0];//0表示已经选过放在cooker中了，所以score[0]是总的分数
//dp[11...11]-(total score-dp[11...11])
printf("%d\n",ans);
}
return 0;
}