题解 P1169 【[ZJOI2007]棋盘制作】

lzoi_lhy · 2018-07-12 15:08:10 · 题解

我是一个既没想到dp又没想到根据坐标奇偶性取反的脑回路有些奇怪的蒟蒻

个人脑洞：

从第一行到第n行扫一遍，维护h数组表示从当前格子往上能延伸到的黑白相间的线段（有一条边长为1的矩形）的最长长度

我们可将当前行分为若干条线段，满足每条线段是最长的黑白相间的线段（不能再向左右延伸）

对于每条线段，结合h数组，我们不难发现我们得到了一排高矮不一的长条状的矩形

是不是很熟悉？用单调栈扫一遍即可

如果遇到颜色与上一个相同的格子，就把整个栈弹出来

注意正方形可以在数矩形的时候顺便数出来

#include<cstdio>
#include<iostream>
#include<cstring>
#define X (h[stack[top]])//矩形的宽 
#define Y (cur-stack[top-1]-1)//矩形的长 
#define Z (min(X,Y))//正方形的边长 
using namespace std;
int n,m,top,cur,ans1,ans2,stack[2010],map[2010][2010],h[2010];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) scanf("%d",&map[i][j]);
    for (int j=1;j<=n;++j){
        for (int i=1;i<=m;++i)
            if (j>1&&map[j][i]!=map[j-1][i]) ++h[i];
            else h[i]=1;
        cur=1;
        while (cur<=m){
            stack[0]=cur-1;stack[top=1]=cur++;
            while (cur<=m&&(map[j][cur]!=map[j][cur-1])){
                while (top&&h[stack[top]]>h[cur])
                    ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
                stack[++top]=cur++;
            }
            while (top) ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
        }
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}