P1169 [ZJOI2007]棋盘制作

方杰123 · 2022-10-12 21:53:56 · 个人记录

题目在这里

思路

这是一类经典套路问题，第一做很难，但第二次做就感觉如履平地。

解决的题目是求最大矩形（正方形）面积。

方法是悬线法。按我自己的理解就是从上到下每个高度做一次从左到右的扫描线，（枚举扫描线最下面的点）而这个矩形则是这根线最上端能到达的点，然后将线左右平移合法构成的最大面积。

预处理l[i][j]，r[i][j]，up[i][j]表示第这个点往上，左，右拓展的最远的点。

然后如果他能继承上面的点（扫描线往上拓展一格），那么就继承上面的矩形。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int n,m,a[N][N],l[N][N],r[N][N],up[N][N];
int ans1,ans2;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)up[i][j]=i,l[i][j]=j,r[i][j]=j;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
            if(a[i][j]^a[i][j-1]){
                l[i][j]=l[i][j-1];
            }
    for(int i=1;i<=n;i++)
        for(int j=m-1;j>=1;j--)
            if(a[i][j]^a[i][j+1]){
                r[i][j]=r[i][j+1];
            }   
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]^a[i-1][j]){
                up[i][j]=up[i-1][j];
            }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]^a[i-1][j] && i!=1){
                up[i][j]=up[i-1][j];l[i][j]=max(l[i][j],l[i-1][j]),r[i][j]=min(r[i][j],r[i-1][j]);
            }//能继承上个点
            int b1=r[i][j]-l[i][j]+1;
            int b2=i-up[i][j]+1;
            int minb=min(b2,b1);
            ans1=max(ans1,minb*minb);
            ans2=max(ans2,b1*b2);
        }
    }
    printf("%d\n%d",ans1,ans2);
    return 0;
}