黑白方块

chen_zhe · 2024-07-03 18:49:59 · 题解

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

:::align{center} :::

先简化问题：如果我们有一个矩形，其左上角顶点为 (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) 的复杂度呢？