luogu 1169 棋盘制作（单调栈/悬线）

luogu 1169 棋盘制作（单调栈/悬线）

首先，一个是棋盘的矩阵，满足相邻两个元素颜色不同。假设左上角的(1,1)是白色的格子。那么易证，横纵坐标之和是偶数的格子是白色的，是奇数的各自是黑色的。所以逆向思维，只要把给定的矩阵，横纵坐标之和同模2的一种格子反色，问题就变成了求最大的同色矩阵和同色正方形。这是最大子矩阵问题。用单调栈可以做，不过比悬线法烦一些。下面我来介绍一下悬线法。

悬线就是一端贴着不可算入矩形的区域（墙壁）的线。首先，一个最大子矩阵中一定有悬线，不然这个矩阵是可以再扩张的。所以，我们只要枚举所有悬线即可。首先n^2预处理出每个点向上向下能扩展的最大距离。然后从左向右，从右向左分别枚举一遍所有悬线（横向的），找出最大值即可。详见代码。

还有，个人感觉这种题目的思路很重要，就是把求最优解，转化为求出每个元素作为基础的最优值，然后取最优值中的最优值作为答案。

#include <cstdio>

using namespace std;

const int maxn=2005, INF=1e9;\

typedef int inta2[maxn][maxn];

int n, m, ans1, ans2, begin, minup, mindown;

inta2 a, up, down;

int max(int x, int y){ return x<y?y:x; }

int min(int x, int y){ return x<y?x:y; }

int sqr(int x){ return x*x; }

int main(){

    scanf("%d%d", &n, &m);

    for (int i=1; i<=n; ++i) //转换棋盘

        for (int j=1; j<=m; ++j){

            scanf("%d", &a[i][j]);

            if (i&1) a[i][j]^=1;

            if (!(j&1)) a[i][j]^=1;

        }

    for (int i=1; i<=n; ++i)

        for (int j=1; j<=m; ++j)

            up[i][j]=(a[i][j]==a[i-1][j]?

                up[i-1][j]+1:1);

    for (int i=n; i>0; --i)

        for (int j=1; j<=m; ++j)

            down[i][j]=(a[i][j]==a[i+1][j]?

                down[i+1][j]+1:1);

    //悬线法

    for (int color=0; color<=1; ++color)

    for (int i=1; i<=n; ++i){

        minup=mindown=INF; begin=1;

        for (int j=1; j<=m; ++j){

            if (a[i][j]!=color){

                minup=mindown=INF;

                begin=j+1; continue;

            }

            minup=min(minup, up[i][j]);

            mindown=min(mindown, down[i][j]);

            ans1=max(ans1, (minup+mindown-1)*(j-begin+1));

            ans2=max(ans2, sqr(min(minup+mindown-1, j-begin+1)));

        }

        minup=mindown=INF; begin=m;

        for (int j=m; j>0; --j){

            if (a[i][j]!=color){

                minup=mindown=INF;

                begin=j-1; continue;

            }

            minup=min(minup, up[i][j]);

            mindown=min(mindown, down[i][j]);

            ans1=max(ans1, (minup+mindown-1)*(begin-j+1));

            ans2=max(ans2, sqr(min(minup+mindown-1, begin-j+1)));

        }

    }

    printf("%d\n%d", ans2, ans1);

    return 0;

}