洛谷P1169[ZJOI2007]棋盘制作

题目

一道悬线法的裸题，悬线法主要是可以处理最大子矩阵的问题。

而这道题就是比较经典的可以用悬线法来处理的题。

而悬线法其实就是把矩阵中对应的每个位置上的元素分别向左向上向右，寻找到不能到达的地方，然后递推或者说是DP，这样在每次递推完之后就可以更新最小值了。

• \([height_{i, j}]\) ：表示以\((i,j)\)为底的悬线的高
• \([left_{i,j}]\) ：表示向左最多能移动到的位置
• \([right_{i,j}]\) ：表示向右最多能移动到的位置

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;

int n, m, ans1, ans2;

int data[1010][1010], lef[1010][1010], righ[1010][1010], height[1010][1010];

int main()

{

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

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

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

		{

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

			lef[i][j] = righ[i][j] = j;

			height[i][j] = 1;

		}

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

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

			if (data[i][j] != data[i][j - 1])

				lef[i][j] = lef[i][j - 1];

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

		for (int j = m - 1; j >= 1; --j)

			if (data[i][j] != data[i][j + 1])

				righ[i][j] = righ[i][j + 1];

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

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

		{

			if (i != 1 && data[i][j] != data[i - 1][j])

			{

				lef[i][j] = max(lef[i][j], lef[i - 1][j]);

				righ[i][j] = min(righ[i][j], righ[i - 1][j]);

				height[i][j] = height[i - 1][j] + 1;

			}

			int a = righ[i][j] - lef[i][j] + 1;

			int b = min(a, height[i][j]);

			ans1 = max(ans1, b * b);

			ans2 = max(ans2, a * height[i][j]);

		}

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

}