BZOJ5248：[九省联考2018]一双木棋—

BZOJ5248：[九省联考2018]一双木棋——题解

阅读量：6412 次

发布时间：2019-06-23

本文共 1470 字，大约阅读时间需要 4 分钟。

菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。棋局开始时，棋盘上没有任何棋子，
两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且
这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上，都写有两个非负整数，从上到下第i行中从左到右第j列的格子上的两个整数记作Aij、Bij。在
游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的Aij之和，牛牛的得分是所
有有白棋的格子上的Bij的和。

菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都
采用最优策略且知道对方会采用最优策略，那么，最终的结果如何

每次添加的棋子构成的形状永远都是一种类梯形的形状，可能状态会少些，更何况n和m才10，于是想到状压dp。

因为棋盘模型能够想到插头dp，那么轮廓线就是显然的棋子的边界。

于是向下的插头为0，向右的插头为1，显然状态才2^(n+m)，记忆化搜即可。

题解讲完了接下来是吐槽时间：

woc我**是脑子抽了吧考试时候就写了一个对抗搜索？？？没写过插头dp可能不是很好想，但是我**好歹学过插头dp啊轮廓线我**怎么没想起来？

完后（知道题解后）我除了很zz的忘写了记忆化搜就是一次A了……

可能我的脑子天生不适合搞OI。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=11;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int n,m,a[N][N],b[N][N],f[1<<(N*2)][2];int dp(int s,int id){ if(f[s][id]!=INF)return f[s][id]; int c[N<<1]={ 0}; int l=-1,tmp=s; while(tmp){ int t=tmp-tmp/2*2;c[++l]=t;tmp>>=1;} l=n+m-1; int ans=id?INF:-INF; int x=0,y=0; for(int i=0;i<=l;i++){ if(!c[i])y++; else x++; if(i&&c[i-1]&&(!c[i])){ tmp=s-(1<
           >1)+(1<