P7741 [AHOI2007] 石块地板 题解
Micnation_AFO
2021-10-16 22:18:50
- [原题面](https://www.luogu.com.cn/problem/P7741)
- [更好的阅读体验](https://mcnt445.blog.luogu.org/solution-p7741)
------------
**题目大意** ：给出一个 $m \times n$ 的矩阵，求出这个矩阵的最大子矩阵和。（把题目中的 $0$ 在读入时当做 $-1$ 处理即可，下文不再赘述）
**具体思路** ：
1. 求出每一行前 $j$ 个数的前缀和。即：
$$sum_{i,j} = sum_{i,j-1} + a_{i,j}$$
其中，$sum_{i,j}$ 表示第 $i$ 行前 $j$ 个数的前缀和。
1. 进行枚举起始列 $i$ 与目标列 $j$，再把每一行中从 $i$ 到 $j$ 的和算出来（利用之前的前缀和），我们可以建立一个 **临时** 数组`f1`，则：
$$f_k = sum_{k,j} - sum_{k,i-1}$$
其中，$f_k$ 表示第 $k$ 行中从 $i$ 到 $j$ 的和。
1. 这时，我们已经把每一行（从 $i$ 到 $j$）的和存到了数组 $f$ 中，那么我们就可以把问题转化为 **最大子段和** 问题了。最大子段和的公式：
$$f_k = \max(f_k, f_k + f_{k - 1})$$
再用变量 $ans$ 打擂台求出 $f_k$ 的最大值即可。
**AC Code** ：
```cpp
#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;
}
```