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;}