题解 P2706 【巧克力】

Froranzen · 2020-12-20 00:54:17 · 题解

题目传送门

1.第一种 O(n^3) 做法

本人第一个想到的做法就是用二维前缀和来暴力查找最大子矩阵。

具体来讲，就是用一个三维的 bool 数组 vis_{i,j,k}，表示在第 i 行的第 j \sim k 个数间是否有 0。然后在查找最大子矩阵时，在上下两边之间跑一遍循环来检查有无 0。

二维前缀和

首先，设 sum_{i,j}，代表从 (1,1) 为左上角到 (i, j) 为右下角的矩形区域的加权和。

令 (i, j) 表示位置为从左往右数第 i 列，从上往下数第 j 行的格子。

根据上图，我们可以得出这样的公式： sum_{i,j} = sum_{i-1,j} + sum_{i,j-1} - sum_{i-1,j-1} + val_{i,j}

因为左下角为 (i - 1, j - 1) 的矩形，在 (i, j - 1) 矩形中加了一次，在 (i - 1, j) 矩形中又加了一次，所以要减去矩形 (i - 1, j - 1) 。

如上图，我们根据 sum 数组的值，可以较为容易地推出下面公式，即点 (i,j) 为左上角，点 (l,r) 为右下角的矩阵中值的和为： sum_{l, r} - sum_{i-1,r} - sum_{l,j-1} + sum_{i-1,j-1}

理解了二维前缀和，这道题就没什么难度了。

代码

#include <cstdio>
#include <cstring>
using namespace std;

int _map[333][333];
int qwq[333][333];  //二维前缀和，维护数值
bool wqw[333][333][333];  //维护有无0
int n, m;
int ans;

inline int min (int a, int b) {
    return a < b ?a :b;
}

inline int max (int a, int b) {
    return a >b ?a :b;
}

int main () {
    scanf ("%d %d", &n, &m);
    for (int i(1); i <= n; ++i)
        for (int j(1); j <= m; ++j)
            scanf ("%d", &_map[i][j]);
    for (int i(1); i <= n; ++i) {
        for (int j(1); j <= m; ++j) {
            qwq[i][j] = qwq[i][j - 1] + qwq[i - 1][j] - qwq[i - 1][j - 1] + _map[i][j];  //二维前缀和
        }
    }
    for (int i(1); i <= n; ++i) {  
        for (int l(1); l <= m; ++l) {  //枚举一个点
            int len = m - l;  //求出剩余长度
            bool flag = false;  //标记
            for (int s(0); s <= len; ++s) {  //循环一遍长度
                if (flag == true) wqw[i][l][l+s] = 1;  //如果之前已经有过'0'，直接记录为有'0'
                if (!_map[i][l + s]) {  //如果当前点是'0'
                    wqw[i][l][l + s] = 1;
                    flag = true;
                }
            }
        }
    }
    for (int i(1); i <= n; ++i) {
        for (int j(1); j <= m; ++j) {  //枚举一个点
            int tmp = m - j;  //求出剩余长度
            bool flag = false;  //标记
            int orz;  //标记
            for (int len(0); len <= tmp; ++len) {  //枚举长度
                for (int k(i); k <= n; ++k) {  //枚举另一个点，因为是一个矩形，所以我们只枚举行数，相应的顶点都是和上面两层枚举的顶点平行
                    if (flag && k == orz) break;  //剪枝，因为len是正序枚举，所以之前有'0'，现在到了当时的行数，一定还会有'0'
                    if (wqw[k][j][j +len]) {  //有0
                        flag = true;
                        orz = k;  //标记
                        break;
                    }
                    ans = max (ans, qwq[k][j +len] - qwq[i - 1][j +len] - qwq[k][j -1] + qwq[i - 1][j - 1]);  //二维前缀和公式
                }
            }
        }
    }
    printf ("%d", ans);
    return 0;
}

upd: 2022.10.17

这样一个暴力题解成了点赞数最多的，感觉有点误导别人了，所以本人在这里补充一下别的做法。

2.另外一种 O(n^3) 做法

首先做一步转化：我们直接将 0 位置的权值赋成负无穷，所以不合法的矩形的权值都变成负无穷了，然后求出新矩形的最大子矩形就是答案。

设 w(l,r,i,j) 表示 (l,r) 为左上端点，(i,j) 为右下端点的矩形权值。

暴力 O(n^2) 枚举上下边界 l, r，再从左往右扫右边界 i，维护最优左边界 j。答案的形式一定是 w(1,l,i,r) - w(1,l,j-1,r)，所以维护一个 w(1,l,i,r) 的最小值即可。

时间复杂度 O(n^3)。

3. O(n^2) 做法

来到正题。给 0 位置赋负无穷然后求最大子矩阵的话，其实有点浪费题目给的性质了，我们能选出的矩形，一定是极大的，因为权值为正，而上面的 O(n^3) 做法却抛弃了这个性质。所以我们还是考虑原来的问题。

考虑最后的矩形会长成一个什么样子：扩展一格上边界一定会使得这个矩形不合法，不然我们再扩展一格上边界显然更优。设扩展一格上边界后，第 x 列会变得不合法，那我们不妨去枚举这个 x。即对于每个点 (i, j)，求出同一列，之前的第一个不合法的位置 (i, k)，然后去扩展这个以 (i, k+1) 为右上端点，(i, j) 为左下端点的矩形直到不能扩展。具体求这个左右边界，可以先求出 (i, j) 在当前行里，能扩展到的边界，然后和同一列上一个矩形的左右边界取交即可。

时间复杂度 O(n^2)。

感谢您的阅读 :)