http://poj.org/problem?id=1085 (题目链接)
题意
A,B两人玩游戏，在一个大三角形上放火柴，若A放上一根火柴后成功组成一个三角形，那么这个三角形就归属于A，并且A被奖励再放一根火柴。最后谁三角形多谁就胜。
给出一个残局，判断是否存在先手必胜策略。
Solution
最近一直在颓，好久没刷题了。。。
这就是神乎其技的极大极小搜索，其实也差不多就是个贪心，基本很少用上，因为很难判断估价函数的正确性。。详情请见：http://blog.****.net/gwq5210/article/details/48163539。
极大极小搜索就是专门用来解决这一类问题的。在这道题中，我们先对于每一个火柴所放置的位置以及由3根火柴组成的三角形打一个表，将初始状态模拟出来。之后进行搜索，我们把 A的三角形个数-B的三角形个数 当做估价函数。而如果当前节点x与其父亲节点为同一个人决策时，x传承其父亲的alpha或者是beta。然后就是套模板了。
代码
// poj1085
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#define MOD 100003
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
/// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
int e[][2]={{1,2},{1,3},{2,4},{2,5},{2,3},{3,5},{3,6},{4,5},{4,7},{4,8},{5,6},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}};
int a[][3]={{0,1,4},{2,3,7},{3,4,5},{5,6,10},{8,9,15},{7,9,11},{11,12,16},{10,12,13},{13,14,17}};
int n,cnt,f[20]; int getid(int x,int y) {
for (int i=0;i<18;i++)
if ((e[i][0]==x && e[i][1]==y) || (e[i][0]==y && e[i][1]==x)) return i;
return -1;
}
int cal() {
int tt=0;
for (int i=0;i<9;i++) if (f[a[i][0]] && f[a[i][1]] && f[a[i][2]]) tt++;
return tt;
}
int maxdfs(int beta,int a,int b);
int mindfs(int alpha,int a,int b) {
if (cnt==18) return a>b ? inf : -inf;
if (a>=5) return inf;
if (b>=5) return -inf;
int tmp=inf;
for (int i=0;i<18;i++) if (!f[i]) {
f[i]=1;cnt++;
int c=cal();
if (c>a+b) tmp=min(mindfs(alpha,a,c-a),tmp);
else tmp=min(maxdfs(tmp,a,b),tmp);
f[i]=0;cnt--;
if (tmp<=alpha) return tmp;
}
return tmp;
}
int maxdfs(int beta,int a,int b) {
if (cnt==18) return a>b ? inf : -inf;
if (a>=5) return inf;
if (b>=5) return -inf;
int tmp=-inf;
for (int i=0;i<18;i++) if (!f[i]) {
f[i]=1;cnt++;
int c=cal();
if (c>a+b) tmp=max(maxdfs(beta,c-b,b),tmp);
else tmp=max(mindfs(tmp,a,b),tmp);
f[i]=0;cnt--;
if (tmp>=beta) return tmp;
}
return tmp;
}
int main() {
int T,t=0;scanf("%d",&T);
while (T--) {
scanf("%d",&n);
memset(f,0,sizeof(f));
cnt=n;
int w=0,ans[2]={0,0};
for (int x,y,i=1;i<=n;i++) {
scanf("%d%d",&x,&y);
int id=getid(x,y);
f[id]=1;
int c=cal();
if (c>ans[0]+ans[1]) ans[w]+=c-ans[0]-ans[1];
else w^=1;
}
int res=0;
if (!w) res=maxdfs(inf,ans[0],ans[1]);
else res=mindfs(-inf,ans[0],ans[1]);
printf("Game %d: %c wins.\n",++t,res==inf ? 'A' : 'B');
}
return 0;
}