題意:求一個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 閱讀(228)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告