题解 P4363 【[九省联考2018]一双木棋chess】

· · 题解

省选的时候想到了怎么压状态却不会后边的dp

最后边的方向全部连反导致只有20pts连暴力都不如

本题题解

首先先阅读一下题面

对于落子的限制条件是，上方和左方的格子要么是棋子要么是边界

那么我们会发现，一个棋子想要存在的条件是上方和左方的所有格子全部被棋子填满

所以任意时刻，棋盘上的棋子构成一个锯齿形

那么我们发现一件事情，尽管棋盘上的棋子个数高达100个

但是锯齿形图形轮廓线的长度最长不过n+m-1

因此一定是要在轮廓线上做一些手脚了，我们需要在2^{n+m-1}的信息量内描述这个轮廓线

然后一种可行的做法是直接记录每一行有多少个格子，用map存下来，这样的话最大值是10^{10}可以用longlong存下去，然后凭借比正解多个log的复杂度可以通过此题

但是这样压状态太暴力了……我们需要想一些优雅的办法

发现我们的轮廓线是联通的，所以一个轮廓线可以看成一个路径，这意味着我们可以使用类似于"路标"的方法描述一个路径，也就是说用类似于“下一步走到哪里+起始点”的方法来告诉我们一条路径

具体来讲，我们使用dp_{i,j}来描述一个轮廓线，i表示第一行所有棋子中最靠右的棋子的列号，j是一个在二进制下有意义的数，如果j的第p位是0，那么我们从i出发，第p步向左走，如果为1，第p步向下走，这样我们就可以从点i出发，走出这条轮廓线(或者说是路径)

那么我们现在终于可以描述一个棋盘了。

下面是博弈论dp的问题

大概的思路就是假装我们可以一步看到结局，然后选择对自己最有利的状态

但是我们其实没办法看到结局，所以我们倒着看，显然棋盘被布满的状态下没有人可以获得新的分数，那么如果我们用dp_{i,j}表示从i，j这个状态向后推演，双方都使用最优策略可以得到的分数差，就可以起到“看到结局的效果”

那么我们会发现，如果这个局面是先手下完以后形成的，那么如何这个局面如何转移的主动权显然是攥在后手的手里，所以此时这个dp值应该由所有后继状态的相对于先手最劣的状态转移过来，也就是所有的后继状态取个min

同理，如果是后手的话，dp值就应该是对于后手最劣的状态转移过来，也就是所有的后继状态取个max

(如果实在分不清楚的话可以minmax都试一遍，哪个过了样例就选哪个)

最后一个问题，怎么转移呢？

我们发现第一是可以记忆化搜索的，但是其实是存在迭代解法的

发现各个状态间的转移关系，如果把状态看作点，转移关系看作边，那么整张图是一张DAG我们的转移顺序其实是拓扑序，所以将所有状态tpsort一遍无脑转移即可

另一个小问题，如何生成后继状态?

我们按照这个状态把这个轮廓线走出来，然后如果存在一个L形，我们就可以去掉一这个L形的尖从而把这个L形变成一个倒L形，然后就是把相邻两个路标取反一下 具体实现一下就是异或上一个3<<几位就行了

实在不会的话可以自己画一下图，思路就是通过撤走一个棋子然后生成后继状态 然后自己画一个图倒一倒就行了

记得特判第一个点，因为第一个点并不存在L形的结构。

另外如果觉得调试麻烦的话可以写一个打印函数直接以字符画的形式打印出轮廓线方便调试

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=20;const int M=524300;
int dp[N][M];int d[N][M];int up;int val[2][N][N];int n;int m;
struct data{int st;int nw;};queue <data> q;int t[N][M];char mp[N][N];
int main()
{
    scanf("%d%d",&n,&m);t[m][(1<<(n-1))-1]=(n*m+1)%2;//记得处理出来每个状态是先手还是后手 
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&val[0][i][j]);}} 
    for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&val[1][i][j]);}}
    for(q.push((data){m,(1<<(n-1))-1});!q.empty();q.pop())//先处理出每个点额度数 
    {
        int st=q.front().st;int nw=q.front().nw;int px=1;int py=st;int ns=nw>>1;
        if((nw&1)==0&&st!=1)//特判第1个点 
        {
            d[st-1][ns]++;t[st-1][ns]=t[st][nw]^1;
            if(d[st-1][ns]==1){q.push((data){st-1,ns});}
        }
        for(int p=nw,i=0;px<n&&py>=1;p>>=1,i++)//生成后继状态 
        {
            if((p&1)==1&&((p>>1)&1)==0)
            {
                ns=py==1?nw^(1<<i):ns=nw^(3<<i);
                d[st][ns]++;t[st][ns]=t[st][nw]^1;
                if(d[st][ns]==1){q.push((data){st,ns});}
            }if(p&1){px++;}else {py--;}
        }dp[st][nw]=t[st][nw]?-0x3f3f3f3f:0x3f3f3f3f;//然后赋个初值 
    }dp[m][(1<<(n-1))-1]=0;
    for(q.push((data){m,(1<<(n-1))-1});!q.empty();q.pop())//按照拓扑序dp 
    {
        int st=q.front().st;int nw=q.front().nw;int px=1;int py=st;int ns=nw>>1;
        if(t[st][nw])//如果这个局面由后手落子形成 
        {
            if((nw&1)==0&&st!=1)
            {
                d[st-1][ns]--;
                if(d[st-1][ns]==0){q.push((data){st-1,ns});}
                dp[st-1][ns]=min(dp[st-1][ns],dp[st][nw]-val[1][1][st]);
            }
            for(int p=nw,i=0;px<n&&py>=1;p>>=1,i++)//具体来讲我们看这个点下方的点是否可以删掉 
            {
                if(p&1==1&&((p>>1)&1)==0)
                {
                    ns=py==1?nw^(1<<i):ns=nw^(3<<i);//额要特判下边界情况以免把最后一个位变成1导致越界 
                    d[st][ns]--;if(d[st][ns]==0){q.push((data){st,ns});}
                    dp[st][ns]=min(dp[st][ns],dp[st][nw]-val[1][px+1][py]);
                }if(p&1){px++;}else {py--;}//然后按照路标移动指针 
            }
        }
        else//然后同理的 
        {
            if((nw&1)==0&&st!=1)
            {
                d[st-1][ns]--;if(d[st-1][ns]==0){q.push((data){st-1,ns});}
                dp[st-1][ns]=max(dp[st-1][ns],dp[st][nw]+val[0][1][st]);
            }
            for(int p=nw,i=0;px<n&&py>=1;p>>=1,i++)
            {
                if(p&1==1&&((p>>1)&1)==0)
                {
                    ns=py==1?nw^(1<<i):ns=nw^(3<<i);
                    d[st][ns]--;if(d[st][ns]==0){q.push((data){st,ns});}
                    dp[st][ns]=max(dp[st][ns],dp[st][nw]+val[0][px+1][py]);
                }if(p&1){px++;}else {py--;}
            }
        }
    }printf("%d",dp[1][0]+val[0][1][1]);return 0;//最后别忘了加上先手最早落的子 
}