HDU 4753 Fishhead’s Little Game (博弈+记忆话搜索) - c++编程基础

题意：给你一个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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
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 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;ijerry "Tom200":"Jerry404");  
    }  
  
    return 0;  
}