P7363 [eJOI 2020 Day2] Dots and Boxes 题解

· · 题解

考虑这个局面的结构，发现由于每个点的度数为 0 或 2，所以可以继续操作的连通块一定构成一些环或者链。

考虑这个游戏的过程，第一步一定是先手在某一个连通块中加一条边，此时后手可以

第一种很好理解，就是尽可能多占当前的格子，而第二种呢？

首先，做第一种操作，注意到做完之后自己转变为了（一个相同子问题的）先手，而先手进行一次操作是得不到格子的，反而是后手拿到了，说明有时是需要避免自己成为先手的。这种时候需要在达到目的的情况下，尽可能占更多格子，也就是第二种策略的目标。

而具体方法，如图，红色为先手选的，后手按照顺序加蓝色的边，注意最后加的那条不会形成新格子，于是在此之后，后手的回合就结束了。

而且这种方法是最优的，也就是对于一个环最少剩 4 个格子，一个链最少剩 2 个。

注意到剩下的部分先手继续操作的话一定会形成新格子，所以先手不能在不开辟新连通块的情况下结束自己的回合，只能在下一个连通块还是先手。

注意有一个特殊情况，对于一个长度 \leq2 的链，若先手选择在中间的边，那么后手无法进行第二种策略。这种情况下，先手显然需要避免后手进行第二种策略，因为这样后手的选择严格变少了，不管对于后手哪种策略更优，对先手来说都是阻止掉好。

那么已经得到了一个关于连通块数指数级的算法，就是状压哪些集合被选了，然后先手枚举选哪个连通块，再枚举后手的策略，转移即可。

接下来，观察到，对于两个同种连通块（环/链），先手一定会选择其中更小的那个。

因为这样可以让后手得到的格子尽可能少，且（对于 \leq 2 的链来说）有可能还可以限制后手的选择，所以一举两得，感性理解上显然是更优的。

（至于不同种类的连通块之间，注意到后手的选择一个最少剩 4 个，一个最少剩 2 个，之间的优劣关系不好只由大小判定，所以是分开的）

于是这两种连通块剩下的一定分别是一个后缀，所以可以设计 dp 状态 dp_{i,j} 代表对于最大的 i 个链，最大的 j 个环构成的子局面，先手最大收益。转移即枚举下一波选环还是链即可。

复杂度 \mathcal{O}(nm(n+m))，（注意到链的块一定有两个位置与网格边缘相邻，所以不超过 n+m 个，环则是最多 nm/4 个）

#include<bits/stdc++.h>
using namespace std;
//dengyaotriangle!

const int maxn=25;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
const int maxm=405;

int n,m;
char _[maxn];
bool a[maxn][maxn][4];
bool vis[maxn][maxn];

int c[maxm],r[maxm],cs,rs;
int dp[maxm][maxm];//c: chain / r: ring

bool ic;
int sz;
void dfs(int x,int y){
    sz++;
    vis[x][y]=1;
    for(int i=0;i<4;i++)if(a[x][y][i]){
        int cx=x+dx[i],cy=y+dy[i];
        if(cx>=1&&cx<=n&&cy>=1&&cy<=m){
            if(!vis[cx][cy])dfs(cx,cy);
        }else ic=1;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n+1;i++){
        cin>>_;
        for(int j=1;j<=m;j++)if(_[j-1]=='0'){
            a[i-1][j][2]=1;
            a[i][j][3]=1;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>_;
        for(int j=1;j<=m+1;j++)if(_[j-1]=='0'){
            a[i][j-1][0]=1;
            a[i][j][1]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j]){
                ic=0;sz=0;
                dfs(i,j);
                if(ic)c[++cs]=sz;
                else if(sz>1)r[++rs]=sz;
            }
        }
    }
    sort(c+1,c+1+cs,greater<int>());sort(r+1,r+1+rs,greater<int>());
    for(int i=0;i<=cs;i++){
        for(int j=0;j<=rs;j++){
            if(i==0&&j==0){dp[i][j]=0;continue;}
            dp[i][j]=INT_MIN;
            if(i){
                int nw=c[i]+dp[i-1][j];//type1
                if(c[i]>=3){
                    nw=max(nw,c[i]-2-(2+dp[i-1][j]));//type2
                }
                dp[i][j]=max(dp[i][j],-nw);
            }
            if(j){
                int nw=max(r[j]+dp[i][j-1]/*type1*/,r[j]-4-(4+dp[i][j-1])/*type2*/);
                dp[i][j]=max(dp[i][j],-nw);
            }
        }
    }
    cout<<dp[cs][rs];
    return 0;
}