洛谷1169 [ZJOI2007]棋盘制作

题意

求 $N\times M$ 的矩阵中最大的 $0/1$ 相间的长方形和正方形面积。

$N,M\le 2000$ 。

题解

悬线法，把是否是障碍物的判断改成相邻格子是否相同即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=2005;
int n,m,s[N][N],l[N][N],r[N][N],up[N][N],ans1,ans2;

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        s[i][j]=read();
        l[i][j]=r[i][j]=j;
        up[i][j]=1;
    }
    for (int i=1;i<=n;i++) for (int j=2;j<=m;j++)
    {
        if (s[i][j]==s[i][j-1]) continue;
        l[i][j]=l[i][j-1];
    }
    for (int i=1;i<=n;i++) for (int j=m-1;j;j--)
    {
        if (s[i][j]==s[i][j+1]) continue;
        r[i][j]=r[i][j+1];
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        if (i>1 && s[i][j]!=s[i-1][j])
        {
            up[i][j]=up[i-1][j]+1;
            l[i][j]=max(l[i][j],l[i-1][j]);
            r[i][j]=min(r[i][j],r[i-1][j]);
        }
        int w=r[i][j]-l[i][j]+1;
        ans2=max(ans2,w*up[i][j]);
        int mn=min(w,up[i][j]);
        ans1=max(ans1,mn*mn);
    }
    return !printf("%d\n%d",ans1,ans2);
}