2015
09-17

# Gems Fight!

Alice and Bob are playing "Gems Fight!":
There are Gems of G different colors , packed in B bags. Each bag has several Gems. G different colors are numbered from color 1 to color G.
Alice and Bob take turns to pick one bag and collect all the Gems inside. A bag cannot be picked twice. The Gems collected are stored in a shared cooker.
After a player ,we name it as X, put Gems into the cooker, if there are S Gems which are the same color in the cooker, they will be melted into one Magic Stone. This reaction will go on and more than one Magic Stone may be produced, until no S Gems of the same color remained in that cooker. Then X owns those new Magic Stones. When X gets one or more new Magic Stones, he/she will also get a bonus turn. If X gets Magic Stone in a bonus turn, he will get another bonus turn. In short,a player may get multiple bonus turns continuously.
There will be B turns in total. The goal of "Gems Fight!" is to get as more Magic Stones than the opponent as possible.
Now Alice gets the first turn, and she wants to know, if both of them act the optimal way, what will be the difference between the number of her Magic Stones and the number of Bob’s Magic Stones at the end of the game.

There are several cases(<=20).
In each case, there are three integers at the first line: G, B, and S. Their meanings are mentioned above.
Then B lines follow. Each line describes a bag in the following format:

n c1 c2 … cn

It means that there are n Gems in the bag and their colors are color c1,color c2…and color cn respectively.
0<=B<=21, 0<=G<=8, 0<n<=10, S < 20.
There may be extra blank lines between cases. You can get more information from the sample input.
The input ends with G = 0, B = 0 and S = 0.

There are several cases(<=20).
In each case, there are three integers at the first line: G, B, and S. Their meanings are mentioned above.
Then B lines follow. Each line describes a bag in the following format:

n c1 c2 … cn

It means that there are n Gems in the bag and their colors are color c1,color c2…and color cn respectively.
0<=B<=21, 0<=G<=8, 0<n<=10, S < 20.
There may be extra blank lines between cases. You can get more information from the sample input.
The input ends with G = 0, B = 0 and S = 0.

3 4 3
2 2 3
2 1 3
2 1 2
3 2 3 1

3 2 2
3 2 3 1
3 1 2 3

0 0 0

3
-3
Hint
For the first case, in turn 2, bob has to choose at least one bag, so that Alice will make a Magic Stone at the end of turn 3, thus get turn 4 and get all the three Magic Stones.


0）。状态中0表示已经取过，取过的部分只对炉子中剩余宝石的数量有影响；1表示没取过，当前状态可以从1里面选一个取而得到下一个状态。

1）。先手-后手的分数，无论什么时候dp[i]都是记录的面对当前局势先手-后手的得分。换手了之后相当于对方变先手我成后手，故要取负。

2）。dp的时候是从小到大dp，但是实际上取的时候是从大向小取的，即先手可以控制局面，先手可以控制下一步达到什么局面，因此一个局面是从所有它取一个背包之后能造成的局面中最有利自己的一个推出的，因此可以一直取最大值。（相当于我一直控制一个局面，这个局面能使得我比对方得分更多，因为面对相同局势两者采取的路径完全一样，先手完全可以猜测出我新造成的局面到底能给我带来多少好处，求这个好处的过程便是dp的过程）。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int dp[(1<<21)+10][9];
int g,b,s;
int v[25][10];
int a[10];

int max(int a,int b)
{
return a>b?a:b;
}

int main()
{
while (scanf("%d%d%d",&g,&b,&s)&&g+b+s)
{
memset(v,0,sizeof(v));
memset(a,0,sizeof(a));
int sum=0;
for (int i=0;i<b;i++)
{
int n;
scanf("%d",&n);
while (n--)
{
int a1;
scanf("%d",&a1);
v[i][a1]++;
a[a1]++;
sum+=a[a1]/s;
a[a1]%=s;
}
}
int mm=(1<<b)-1;
for (int i=1;i<=g;i++)
dp[0][i]=a[i];      //全部取完炉子的状态
dp[0][0]=0;
for (int i=1;i<=mm;i++)
dp[i][0]=-1000000;
for (int i=0;i<=mm;i++)
{
for (int j=0;j<b;j++)
{
int x=(1<<j);
if ((i&x)==0)   //如果j取过了
{
int gs=0;
for (int k=1;k<=g;k++)  //从没取j到取j总过得到多少宝石
{
a[k]=dp[i][k]-v[j][k];
while (a[k]<0)  //说明取的时候获得了宝石
{
gs++;
a[k]+=s;
}
dp[i^x][k]=a[k];
}
if (gs>0)   //如果大于0，不换手，先手+gs-后手=gs+dp[i][0]
dp[i^x][0]=max(dp[i^x][0],gs+dp[i][0]);
else    //换手，新得到的分数等于0，原来的先手-后手变成后手-先手，取负即可
dp[i^x][0]=max(dp[i^x][0],-dp[i][0]);
}
}
}
printf("%d\n",dp[mm][0]);
}
}