## hdu 4778 Gems Fight!（壮压&记忆化DP）

2018年03月18日 ⁄ 综合 ⁄ 共 3843字 ⁄ 字号 评论关闭

# Gems Fight!

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others)
Total Submission(s): 364    Accepted Submission(s): 159

Problem Description
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.

Input
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.

Output
One line for each case: the amount of Alice's Magic stones minus the amount of Bob's Magic Stones.

Sample Input
```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```

Sample Output
```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.
```

Source

Recommend
We have carefully selected several similar problems for you:  4780 4779 4777 4776 4775

A和B一起玩游戏。这儿有B个袋子。每个袋子里装有一定量的宝石。有G种颜色的宝石。游戏规则是。A和B轮流从袋子中选一袋宝石。然后将它们倒到公共的容器中。若颜色相同的宝石的个数大于等于S那么每S个石头形成一颗魔法石。并且获得再拿一次的机会。规则同上。每一次获得魔法石的个数即为该次的得分。然后问A和B都采用最优的策略(都使自己得分最多)。A的分数和B的得分的差值。

```#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
typedef __int64 ll;
//#progma comment(linker,"/STACK:1024000000,1024000000")
int g,b,s;
int ba[25][10];//存每袋宝石对应颜色的个数
int dp[1<<21|1];
long long op=(1<<5)-1;
int sa[25],tail;
int dfs(int bag,long long nst,int mp)//bag为袋子的使用情况。nst为公共容器里的宝石状态
{
int p,pos,t,st,ans=-1,tans;
long long ns,tt;
if(dp[bag]!=-1)
return dp[bag];
for(p=0;p<b;p++)
{
t=1<<p;//枚举选择的袋子号
if(t&bag)
{
tt=nst;
tans=ns=0;
pos=1;//pos为颜色号
tail=0;
while(pos<=g)//注意这里需取出每一种颜色的个数
{
st=tt&op;
tans+=(st+ba[p][pos])/s;
st=(st+ba[p][pos])%s;
sa[tail++]=st;
tt>>=5;
pos++;
}
while(tail>0)//生成新状态
{
ns<<=5;
ns|=sa[tail-1];
tail--;
}
if(tans>=1)
tans+=dfs(bag-t,ns,mp-tans);//mp为剩下宝石能得的最大分
else
tans=mp-dfs(bag-t,ns,mp-tans);//剩下最大分减下个人的最大得分就为自己的得分了
ans=max(ans,tans);
}
}
return dp[bag]=ans;
}
int main()
{
int i,j,n,c,mp,ans,t;

//freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&g,&b,&s),b||g||s)
{
memset(ba,0,sizeof ba);
memset(dp,-1,sizeof dp);
dp[0]=0;//开始傻逼了没初始化。。。
mp=0;
for(i=0;i<b;i++)
{
scanf("%d",&n);
while(n--)
{
scanf("%d",&c);
ba[i][c]++;
}
}
for(i=1;i<=g;i++)
{
t=0;
for(j=0;j<b;j++)
t+=ba[j][i];
mp+=t/s;
}
ans=dfs((1<<b)-1,0,mp);
ans=2*ans-mp;
printf("%d\n",ans);
}
return 0;
}
```