[ZJOI 2007] 棋盘制作

题目大意

给定一个 $n \times m$ 的黑白网格，在其上找一个面积最大的正方形、矩形的黑白相间的网格，输出最大面积。

$1 \leqslant n, \; m \leqslant 2,000$

题目链接

【ZJOI 2007】棋盘制作 - Luogu 1169

题解

悬线法。

对每个格子 $(i, j)$ ，求出 $up(i, j)$ 、$left(i, j)$ 、$right(i, j)$ 分别表示从该格子向上最远能取多远、以及在取这么远的情况下能向左／右拓展到的最远位置。

$up(i, j) = \begin{cases} 1 \qquad i = 1 \; or \; (i, j) = (i - 1, j) \\ up(i - 1, j) + 1 \qquad (i, j) \neq (i - 1, j) \\ \end{cases} \\ left(i , j) = \begin{cases} lo \qquad i= 1 \; or \;(i, j) = (i - 1, j) \\ max(left(i - 1, j), \; lo) \qquad (i, j) \neq (i - 1, j) \\ \end{cases} \\ right(i , j) = \begin{cases} ro \qquad i = 1 \; or \; (i, j) = (i - 1, j) \\ max(right(i - 1, j), \; ro) \qquad (i, j) \neq (i - 1, j) \\ \end{cases} \\$

其中，$lo$ 每行从左开始计算，表示当前格向左最远能到的位置，$ro$ 与之相反。

扫一遍网格即可求出以上三个数组。此时，对于每个格子 $(i, j)$ ，$up(i, j) \times (right(i, j) - left(i, j) + 1)$ 表示该点能扩展出的最大的黑白相间的矩形。

代码

#include <cstdio>
#include <algorithm>
const int MAXN = 2005;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    static int mat[MAXN][MAXN], up[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        scanf("%d", &mat[i][j]);
        if (i == 1 || mat[i][j] == mat[i - 1][j]) up[i][j] = 1;
        else up[i][j] = up[i - 1][j] + 1;
    }
    for (int i = 1; i <= n; i++) {
        int lo = 1; 
        for (int j = 1; j <= m; j++) {
            if (j == 1) {
                left[i][j] = 1;
                continue;
            }
            if (mat[i][j] == mat[i][j - 1]) lo = j;
            left[i][j] = lo;
            if (up[i][j] > 1) left[i][j] = std::max(left[i - 1][j], lo);
        }
    }
    for (int i = 1; i <= n; i++) {
        int ro = m;
        for (int j = m; j; j--) {
            if (j == m) {
                right[i][j] = m;
                continue;
            }
            if (mat[i][j] == mat[i][j + 1]) ro = j;
            right[i][j] = ro;
            if (up[i][j] > 1) right[i][j] = std::min(right[i - 1][j], ro);
        }
    }
    int ansSqr = 0, ansRect = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        int bottom = right[i][j] - left[i][j] + 1;
        int height = up[i][j];
        ansRect = std::max(ansRect, bottom * height);
        ansSqr = std::max(ansSqr, std::min(bottom, height) * std::min(bottom, height));
    }
    printf("%d\n%d\n", ansSqr, ansRect);
    return 0;
}