题意:求一个n*n矩阵的最大子矩阵。
解题思路:类似一维情况下的最大连续子串。
代码:
#include <cstdio>#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110;
int n, a[maxn][maxn], r[maxn][maxn] , f[maxn];
int main() {
while(~scanf("%d", &n)) {
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d", &a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
r[i][j] = r[i-1][j] + a[i][j];
int ans = a[0][0];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++) {
if(f[k-1] < 0) {
f[k] = r[j][k] - r[i-1][k];
} else {
f[k] = f[k-1] + r[j][k] - r[i-1][k];
}
if(f[k] > ans) ans = f[k];
}
printf("%d\n", ans);
}
return 0;
}
posted on 2015-03-31 23:15
JulyRina 阅读(216)
评论(0) 编辑 收藏 引用 所属分类:
解题报告