自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:29，当前版本为作者最后更新于2024-07-03 18:49:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

先简化问题：如果我们有一个矩形，其左上角顶点为 $(xa,ya)$（即第 $xa$ 行第 $ya$ 列），右下角顶点为 $(xb,yb)$（即第 $xb$ 行第 $yb$ 列），我们如何判断这个矩形范围中 $0$ 和 $1$ 的数量相等呢？

这个问题可以使用二重循环解决，参考代码如下：

bool check(int xa, int ya, int xb, int yb) {
	int a[2] = {0, 0};
	for (int i = xa; i <= xb; i++) {
		for (int j = ya; j <= yb; j++)
			a[w[i][j]]++;
	}
	return a[0] == a[1];
}

在 check 函数中，使用了一个数组，利用“桶计数”思想统计了范围中的 $0$ 和 $1$ 的个数。如果返回值为 true，则说明矩形中 $0,1$ 个数相等，否则不相等。

回到原本的问题中来。如果我们能够对每一个“子矩形”进行 check，判断每个子矩形中 $0$ 和 $1$ 的个数是不是相等，问题就解决了。那么我们如何枚举子矩形呢？我们可以使用四个 for 循环。即：使用两个 for 循环枚举矩形左上角顶点 $(i,j)$，使用两个 for 循环枚举矩形右下角顶点 $(i_1,j_1)$。接着，我们将这个区域使用 check(i,j,i1,j1) 判断区域内是否 $0,1$ 个数相等。

这个矩形的大小怎么统计呢？自然是 $(i_1-i+1)\times (j_1-j+1)$ 了。我们找到最大的子矩形输出即可。

int ans = 0;
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		for (int ii = i; ii <= n; ii++) {
			for (int jj = j; jj <= m; jj++) {
				if (check(i, j, ii, jj))
					ans = max(ans, (ii - i + 1) * (jj - j + 1));
			}
		}
	}
}
cout << ans << endl;

思考题：上述做法的时间复杂度是 $O(n^6)$ 的，它使用了六重循环嵌套。你是否有方法将其优化到不超过 $O(n^4)$ 的复杂度呢？