HDU 4753 Fishhead’s Little Game (博弈+记忆话搜索)
题意：给你一个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 易做图(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-易做图(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=易做图(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;
}
补充：软件开发 , C++ ,
