题解 [ZJOI2007]棋盘制作

把悬线法这个坑填了，还是很简单的 qwq。

悬线法一般解决有一定约束条件的最大矩形问题。悬线的定义是从一个点一直往上走直到边界或者不符合条件结束。

炒个例子，在这题里面比如说有这样一个矩形

则第 \(4\) 行第 \(3\) 列的点的悬线就是这个

1

0

1(这就是起始的点

我们定义 \(up_{i, j}\) 为 \(i\) 行 \(j\) 列的点的悬线长度。

显而易见，如果可以转移，则有 \(up_{i, j} = up_{i - 1, j} + 1\)。

由于是矩形，我们还要枚举悬线往左移动能到的极远处于往右移动的极远处。

令 \(le_{i, j}\) 为第 \(i\) 行 \(j\) 列的点的悬线往左移动的极远处，\(ri_{i, j}\) 是往右的极远处。

如果 \(a_{i, j} \not = a_{i - 1, j}\)，则有 \(le_{i, j} = \max\{le_{i, j}, le_{i - 1, j}\}, ri_{i, j} = \min\{ri_{i, j}, ri_{i - 1, j}\}\)。

为什么左边界取 \(\max\)，右边界取 \(\min\) 呢？这不是求最近的边界吗？

其实这很好理解，首先我们画个图（丑陋预警（

拿这玩意儿画网格图我是什么个天才（悲

点 F 是我们当前所在的点，，我们假设 F 在第 \(i\) 行 \(j\) 列。EF 是 F 的悬线。CD 代表 EF 目前往左移动更新的极远处，GH 代表 EF 目前往右移动更新的极远处，AB 代表 \(i - 1\) 行 \(j\) 列的悬线往左的极远处，IJ 代表往右的极远处。

显然，我们的 CD 应该被更新成 AB，GH 应该被更新成 IJ。原因很简单，以 AB 为例，AB 已经被更新过了，是极左的，那么它为什么没有更新到 CD 那一行呢，因为 CD 与 AB 之间出现了不合法的，那么我们就不能更新到 AB，得更新到 CD。GH 与 IJ 的更新同理。

那么问题又来了，这能保证是极远处吗？显然可以。证明和上面差不多，不写了。

还有一个问题，我发现基本上所有的文章都没有提到，只是在代码里面写了怎么可以这样（恼，还有一个问题，还是上面那张图

。

图逐渐走向艺术派

我们会发现我们的方程没有考虑这里的红色部分是否合法。所以我们要在之前提前处理。如果可以 \(a_{i, j} \not = a_{i, j - 1}\)，则 \(le_{i, j} = le_{i, j - 1}\)（这里 \(j\) 正序枚举）。如果 \(a_{i, j} \not = a_{i, j + 1}\) 则 \(ri_{i, j} = ri_{i, j + 1}\)（这里 \(j\) 倒序枚举）

这个应该很好理解因为我语文不好其实是懒我就不多解释了 qwq

代码：

//SIXIANG

#include <iostream>

#define MAXN 2000

#define QWQ cout << "QWQ" << endl;

using namespace std;

int a[MAXN + 10][MAXN + 10], up[MAXN + 10][MAXN + 10], le[MAXN + 10][MAXN + 10], ri[MAXN + 10][MAXN + 10];

int main() {

	int n, m;

	cin >> n >> m;

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

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

			cin >> a[p][i];

			up[p][i] = 1;

			le[p][i] = ri[p][i] = i;

		}

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

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

			if(a[p][i] != a[p][i - 1])

				le[p][i] = le[p][i - 1];

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

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

			if(a[p][i] != a[p][i + 1])

				ri[p][i] = ri[p][i + 1];

	int ans1 = 0, ans2 = 0;

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

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

			if(p > 1 && a[p][i] != a[p - 1][i]) {

				up[p][i] = up[p - 1][i] + 1;

				le[p][i] = max(le[p][i], le[p - 1][i]);

				ri[p][i] = min(ri[p][i], ri[p - 1][i]);

			}

			int a = up[p][i], b = ri[p][i] - le[p][i] + 1;

			int c = min(a, b);

			ans1 = max(ans1, c * c);

			ans2 = max(ans2, a * b);

		}

	}

	cout << ans1 << ' ' << ans2 << endl;

}

其它题目就可以用类似的板子套上去（所以我就理直气壮的不写啦（

巴特西

题解 [ZJOI2007]棋盘制作

最新文章

热门文章