题意:给出一个矩阵(100×100)求一个子矩阵,使得子矩阵中各个元素的和最大。
分析:类似最大子段和,我们可以将这个矩阵一些列的集合,如果最优解(最大子矩阵)左起第i列,右止于第j列,上下边界先不管。那么我们相当于把这些列的对应位加和,成为一列。并对改列求最大子段和即可。这样我们只需要枚举所有的i和j,然后合并列,然后求最大子段和,取最大即可。
View Code
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; #define maxn 105 #define inf 0x3f3f3f3f int n, array[maxn][maxn]; int f[maxn][maxn][maxn]; void input() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &array[i][j]); } int work() { memset(f, 0, sizeof(f)); int ret = -inf; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { int sum = 0; for (int k = j; k <= n; k++) { sum += array[i][k]; f[i][j][k] = max(f[i - 1][j][k] + sum, sum); ret = max(ret, f[i][j][k]); } } return ret; } int main() { // freopen("t.txt", "r", stdin); input(); printf("%d\n", work()); return 0; }