AtCoder

Luogu

分析

首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度，然而显然是过不去的。

注意到答案在 $\log nm$ 级别，因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时，上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移
$$
dp_{i,j,k,l}=\max\left\{dp_{i-1,j,k,dp_{i-1,j,k,l}},\max_{t=j}^{k-1}\left\{\min\{dp_{i,j,t,l},dp_{i,t+1,k,l}\}\right\}\right\}
$$
如果暴力转移总时间复杂度为 $\mathcal{O}(n^4\log n)$，仍然无法通过。

注意到当 $t$ 增大时 $dp_{i,j,t,l}$ 会减小，$dp_{i,t+1,k,l}$ 会增大，因此只要二分使得两者最接近的 $t$ 即可。总时间复杂度 $\mathcal{O}(n^3\log^2 n)$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=185+10;

int n,m;
char a[N][N]; int s[N][N];
int dp[2][N][N][N];

int same(int lx,int ly,int rx,int ry) {
    int o=s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1];
    return o==(rx-lx+1)*(ry-ly+1)||o==0;
}

int f(int o,int i,int j,int k) {
    int L=i,R=j-1,res=0;
    while (L<=R) {
        int mid=(L+R)>>1;
        res=max(res,min(dp[o][i][mid][k],dp[o][mid+1][j][k]));
        if (dp[o][i][mid][k]<dp[o][mid+1][j][k]) R=mid-1;
        else L=mid+1;
    }
    return res;
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) scanf("%s",a[i]+1);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]=='#');
    if (same(1,1,n,m)) { puts("0"); return 0; }
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;++j)
            for (int k=1,t;k<=m;k=t) {
                t=k;
                while (t<=m&&same(i,k,j,t)) ++t;
                for (int p=k;p<t;++p) dp[0][i][j][p]=t-1;
                if (k==t) dp[0][i][j][k]=k-1,++t;
            }
    for (int w=1;;++w) {
        int o=w&1,p=o^1;
        for (int i=1;i<=n;++i)
            for (int j=i;j<=n;++j)
                for (int k=1;k<=m;++k) {
                    int t=dp[p][i][j][k];
                    if (t==m) dp[o][i][j][k]=m;
                    else dp[o][i][j][k]=max(dp[p][i][j][t+1],f(p,i,j,k));
                }
        if (dp[o][1][n][1]==m) { printf("%d\n",w); break; }
    }
    return 0;
}