首页 > 代码库 > hdu 4778 Gems Fight!（状态压缩+博弈+记忆化）

hdu 4778 Gems Fight!（状态压缩+博弈+记忆化）

2024-07-31 11:05:00   225人阅读

Gems Fight!

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


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.

题意：有b个袋子，袋子中装有一些不同颜色的宝石，两个人轮流一个袋子把宝石放入cooker，若有s个宝石颜色相同，这个人得到一分，这 s个宝石消失;且某次得到分数，则可以再取一次。求先手和后手的最大差值。

解题思路：因为最多只有21个袋子，可以考虑状态压缩，且给定袋子宝石数量，可知两个人的总得分是固定的。对于每个状态dp[s]表示当前状态下先手能获得的最大分数，然后，枚举该状态下先手可取的每个袋子作为第一次选择，若选择该袋子能得到分数sum，则先手再取一次，dp[s]=sum+dfs（s^(1<<i),left-sum,c);否则，先手得到分数为当前剩余分数减去后手能得到的分数dp[s]=left-dfs(s^(1<<i),left,c)；


#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std;
#define LL __int64
#define N 25
const int inf=-0x1f1f1f1f;
int g,b,s;
int box[25][10];
int dp[1<<21];
int dfs(int S,int left,int c[])
{
    if(dp[S]!=inf)
        return dp[S];
    if(S==0||left==0)
        return 0;
    int ans=0,i;
    int a[10];
    for(i=0;i<b;i++)
    {
        int sum=0;
        if(S&(1<<i))
        {
            int tmp=S^(1<<i),cnt;
            for(int j=1;j<=g;j++)
            {
                a[j]=c[j]+box[i][j];
                sum+=a[j]/s;
                a[j]%=s;
            }
            if(sum)
                cnt=sum+dfs(tmp,left-sum,a);
            else
                cnt=left-dfs(tmp,left,a);
            ans=max(ans,cnt);
        }
    }
    return dp[S]=ans;
}
int main()
{
    int i,x,m;
    int num[10];
    while(scanf("%d%d%d",&g,&b,&s),g||b||s)
    {
        memset(box,0,sizeof(box));
        memset(num,0,sizeof(num));
        for(i=0;i<b;i++)
        {
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&x);
                box[i][x]++;
                num[x]++;
            }
        }
        int sum=0;
        for(i=1;i<=g;i++)
            sum+=num[i]/s;
        for(i=0;i<(1<<b);i++)
            dp[i]=inf;
        int c[10];
        memset(c,0,sizeof(c));
        int ans=dfs((1<<b)-1,sum,c);
        printf("%d\n",ans*2-sum);
    }
    return 0;
}












hdu 4778 Gems Fight!（状态压缩+博弈+记忆化）


联系
我们