对抗搜索/dp-hdu-4753-Fishhead’s Little Game
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4753
题目意思：
在3*3的方格中，有4*4=16个点，标号分别为1~16，A、B两人轮流玩游戏，每次可以添加一条边（相邻节点），如果恰好能够凑成一个边长为1的正方形则得一分，两个的话得2分。给定两人放的n边后，求最终格局谁会胜。
解题思路：
状态压缩＋对抗搜索。（对抗搜索做少了）
和今年通话邀请赛这题很像：http://blog.csdn.net/cc_again/article/details/10284769
除去给定的ｎ条边，还剩下不到１２条边S，所以可以状态压缩，dp[i]表示，S中放了边的状态为i的情况下，先走还能获得的最大分数。
每次dfs维护一个剩余的分数sum，表示当前状态下能获得的最大分数，dp[s]=max(sum-走一步后对手获得的最大分数）;
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#define eps 1e-6#define INF 0x3fffffff#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;int dp[1<<12];//dp[i]表示走了i状态的边，还能获得的最大分数bool hav[20][20];int n;bool iscan(int aa,int bb,int b,int a) //能否围城正方形{ if(hav[aa][bb]&&hav[bb][b]&&hav[b][a]&&hav[a][aa]) return true; return false;}struct Edge{ int x,y;};vector<Edge>myv;int ok1(int a,int b)//横着的情况{ int aa=a-4,bb=b-4,res=0; if(aa>=0&&bb>=0) //上 { if(iscan(aa,bb,b,a)) res++; } aa=a+4,bb=b+4; if(aa<16&&bb<16) //下 { if(iscan(aa,bb,b,a)) res++; } return res;}int ok2(int a,int b){ int res=0; int aa,bb; aa=a-1,bb=b-1; if(bb%4!=3) //aa可能为负数 左 { if(iscan(a,b,bb,aa)) res++; } aa=a+1,bb=b+1; //右 if(aa%4) { if(iscan(a,b,bb,aa)) res++; } return res;}int dfs(int ord,int s,int sum){ if(ord==25||sum<=0) //分数已经得完了 return 0; if(dp[s]!=-1) //记忆话搜索 return dp[s]; int res=0; for(int i=0;i<myv.size();i++) { if((1<<i)&s) continue; hav[myv[i].x][myv[i].y]=true; hav[myv[i].y][myv[i].x]=true; if(myv[i].x==myv[i].y-1) //行 res=max(res,sum-dfs(ord+1,s|(1<<i),sum-ok1(myv[i].x,myv[i].y))); else res=max(res,sum-dfs(ord+1,s|(1<<i),sum-ok2(myv[i].x,myv[i].y))); hav[myv[i].x][myv[i].y]=false; hav[myv[i].y][myv[i].x]=false; } dp[s]=res; return res;}int main(){ int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { scanf("%d",&n); memset(hav,false,sizeof(hav)); myv.clear(); int pa=0,pb=0,a,b; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); a--,b--; hav[a][b]=hav[b][a]=true; if(a>b) swap(a,b); if(a==b-1) //在同一行 { if(i&1) pa+=ok1(a,b); else pb+=ok1(a,b); } else//同一列 { if(i&1) pa+=ok2(a,b); else pb+=ok2(a,b); } } for(int i=0;i<16;i++) //统计剩下的边 for(int j=i+1;j<16;j++) { if(hav[i][j]) continue; if(i==j-1&&j%4) { Edge p; p.x=i,p.y=j; myv.push_back(p); } if(i==j-4) { Edge p; p.x=i,p.y=j; myv.push_back(p); } } //printf("%d %d\n",pa,pb); memset(dp,-1,sizeof(dp)); if(n<24) { if((n+1)&1) //当前谁先走 { pa+=dfs(n+1,0,9-pa-pb); pb=9-pa; } else { pb+=dfs(n+1,0,9-pa-pb); pa=9-pb; } } //printf("ljdj\n"); //printf("%d %d\n",pa,pb); printf("Case #%d: %s\n",ca,pa>=5?"Tom200":"Jerry404"); } return 0;}