P7741 [AHOI2007] 石块地板 题解

· · 题解

题目大意 ：给出一个 m \times n 的矩阵，求出这个矩阵的最大子矩阵和。（把题目中的 0 在读入时当做 -1 处理即可，下文不再赘述）

具体思路 ：

  1. 求出每一行前 j 个数的前缀和。即：

    sum_{i,j} = sum_{i,j-1} + a_{i,j}

    其中，sum_{i,j} 表示第 i 行前 j 个数的前缀和。

  2. 进行枚举起始列 i 与目标列 j，再把每一行中从 i 到 j 的和算出来（利用之前的前缀和），我们可以建立一个 临时 数组f1，则：

    f_k = sum_{k,j} - sum_{k,i-1}

    其中，f_k 表示第 k 行中从 i 到 j 的和。

  3. 这时，我们已经把每一行（从 i 到 j）的和存到了数组 f 中，那么我们就可以把问题转化为 最大子段和 问题了。最大子段和的公式：

    f_k = \max(f_k, f_k + f_{k - 1})

    再用变量 ans 打擂台求出 f_k 的最大值即可。

AC Code ：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 405
int m, n, ans;
int sum[maxn][maxn], f[maxn];
char c;

signed main() {
    cin >> m >> n;
    //注意不是 n 行 m 列

    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) {
            cin >> c;
            if (c == '1') sum[i][j] = sum[i][j - 1] + 1;
            else if (c == '0') sum[i][j] = sum[i][j - 1] - 1;
        }
    //求出每一行的前 j 个数的前缀和

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {//枚举第 i 列到第 j 列

            for (int k = 1; k <= m; k++) 
                f[k] = sum[k][j] - sum[k][i - 1];//把每一行的和算出来

            for (int k = 1; k <= m; k++) {
                f[k] = max(f[k], f[k] + f[k - 1]);
                ans = max(ans, f[k]);
            }//最大子段和问题

        }
    cout << ans << endl;
    return 0;
}