poj 1085 Triangle War 博弈论+记忆化搜索

思路：总共有18条边，9个三角形。

极大极小化搜索+剪枝比较慢，所以用记忆化搜索！！

用state存放当前的加边后的状态，并判断是否构成三角形，找出最优解。

代码如下：

 #include<iostream>

 #include<stdio.h>

 #include<algorithm>

 #include<iomanip>

 #include<cmath>

 #include<cstring>

 #include<vector>

 #define inf 1<<25

 using namespace std;

 int edge[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,},{,}

 ,{,},{,},{,}};

 int tri[][]={{,,},{,,},{,,},{,,},{,,},{,,},{,,},{,,},{,,}};

 int p[],dp[<<];

 int cal(int state,int e)

 {

       int ans=;

       for(int i=;i<;i++){

             bool flag=;

             for(int j=;j<;j++) //判断边e是否在这个三角形中

                   if(e==tri[i][j]) flag=true;

             if(flag){ //e在这个三角形中

                   for(int j=;j<;j++){

                         if(!(p[tri[i][j]]&state||e==tri[i][j])){ //如果满足条件说明tri[i][j]这条边不存在且e也不是这条边

                               ans--;break;                               //也就是不能构成三角形，否则能构成

                         }

                   }

                   ans++;

             }

       }

       return ans;

 }

 int dfs(int state)

 {

       if(dp[state]!=-inf) return dp[state];

       int ans=-inf;

       for(int i=;i<;i++){

             if(!(state&p[i])){

                   int tt=cal(state,i);

                   if(tt) tt+=dfs(state|p[i]);

                   else tt-=dfs(state|p[i]);

                   ans=max(ans,tt);

             }

       }

       return dp[state]=ans;

 }

 int main()

 {

       //freopen("1.txt","r",stdin);

     int t,u,v,ca=,m;

     p[]=;

     for(int i=;i<;i++) p[i]=p[i-]*;

     for(int i=;i<(<<);i++) dp[i]=-inf;

     dp[(<<)-]=;

     scanf("%d",&t);

     while(t--){

             scanf("%d",&m);

             int m0=,m1=,tt=,state=,side=;

             while(m--){

                   scanf("%d%d",&u,&v);

                   for(int i=;i<;i++)

                         if(edge[i][]==u&&edge[i][]==v){

                               tt=cal(state,i);

                               state|=p[i];

                               side==?m0+=tt:m1+=tt;

                               side++;

                               if(tt) side++;

                               side%=;

                               break;

                         }

             }

             int ans=m0-m1;

             if(side==) ans+=dfs(state);

             else ans-=dfs(state);

             printf("Game %d: %s\n",++ca,ans>?"A wins.":"B wins.");

     }

     return ;

 }