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