HDU 4753 Fishhead’s Little Game (博弈+记忆话搜索)

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4753

题意：给你一个4*4的格子16个点，两个人博弈，每次可以添加一条边，当添加一条边后围成1*1的正方形时就加一分，现在已经给你n个回合，问你到最后谁将得的分最高（两个人都是很聪明，每一步都是最优的）。

题解：因为12<=n<=24，所以剩下的边最多只有12条，用状态压缩即可(2^12)

dp[i]表示，S中放了边的状态为i的情况下，先走还能获得的最大分数。

每次dfs维护一个剩余的分数sum，表示当前状态下能获得的最大分数，dp[s]=max(sum-走一步后对手获得的最大分数)

注意一点他们两的得分之和为9，因为只有9个1*1的正方形。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s)  scanf("%s",s)
#define pi1(a)    printf("%d\n",a)
#define pi2(a,b)  printf("%d %d\n",a,b)
#define mset(a,b)   memset(a,b,sizeof(a))
#define forb(i,a,b)   for(int i=a;i<b;i++)
#define ford(i,a,b)   for(int i=a;i<=b;i++)

typedef __int64 LL;
const int N=22;
const int M=1000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;

struct node
{
    int x,y;
}w;

int n;
int edge[N][N],dp[M],use[N];
vector<node> mp;

int fuck(int a,int b)
{
    int sum=0;
    if(a>b) swap(a,b);
    if((b-a)==1)    //横着的
    {
        if(a>=1&&a<=4)
        {
            int aa=a+4,bb=b+4;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
        else if(a>=13&&a<=16)
        {
            int aa=a-4,bb=b-4;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
        else
        {
            int aa=a+4,bb=b+4;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
            aa=a-4,bb=b-4;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
    }
    else    //竖着的
    {
        if(a%4==1)
        {
            int aa=a+1,bb=b+1;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
        else if(a%4==0)
        {
            int aa=a-1,bb=b-1;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
        else
        {
            int aa=a+1,bb=b+1;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
            aa=a-1,bb=b-1;
            if(edge[aa][a]&&edge[aa][bb]&&edge[bb][b])
                sum++;
        }
    }
    return sum;
}

int dfs(int now,int st,int last)
{
    if(now>=25)//结束
        return 0;

    if(dp[st]!=-1)//记忆话搜索
        return dp[st];

    int ma=0;
    for(int i=0;i<mp.size();i++)
    {
        if(use[i])  continue;
        int x=mp[i].x,y=mp[i].y;

        edge[x][y]=edge[y][x]=1;
        use[i]=1;
        ma=max(ma,last-dfs(now+1,st|(1<<i),last-fuck(x,y)));
        use[i]=0;
        edge[x][y]=edge[y][x]=0;
    }

    dp[st]=ma;
    return ma;
}

int main()
{
//    freopen("input.txt","r",stdin);
    int T,ca=0;
    si1(T);
    while(T--)
    {
        int tom=0,jerry=0;
        mset(edge,0);
        si1(n);
        ford(i,1,n)
        {
            int a,b;
            si2(a,b);
            edge[a][b]=edge[b][a]=1;
            int k=fuck(a,b);
            if(i&1) tom+=k;
            else jerry+=k;
        }

        mp.clear();
        ford(i,1,16)    //统计剩下的边
            ford(j,i+1,16)
            {
                if(edge[i][j])  continue;
                if((j-i)==1&&i%4!=0){w.x=i;w.y=j;mp.push_back(w);}
                if((j-i)==4){w.x=i;w.y=j;mp.push_back(w);}
            }
        mset(dp,-1);
        mset(use,0);
        if((n+1)<=24)   //tom+jerry=9
        {
            if((n+1)&1)
            {
                tom+=dfs(n+1,0,9-tom-jerry);
                jerry=9-tom;
            }
            else
            {
                jerry+=dfs(n+1,0,9-jerry-tom);
                tom=9-jerry;
            }
        }
        printf("Case #%d: %s\n",++ca,tom>jerry?"Tom200":"Jerry404");
    }

    return 0;
}