可以用前缀和容斥优化到 \(O(n^4)\),但是不够进行如下图操作:
将每一列的数值都压缩到一维的数组上,就转换为求最大字段和问题,时间复杂度 \(O(n^3)\)。
看看代码就知道了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int a[505][505];
ll b[505];
int main(){
ios::sync_with_stdio(false);
cin>>m>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
ll ans=INT_MIN;
for(int l=1;l<=n;l++){
memset(b,0,sizeof b);//起点变了,清零。
for(int r=l;r<=n;r++){
for(int k=1;k<=m;k++){//合并位一维数组
b[k]+=a[r][k];
}
ll mx=INT_MIN;
ll cmx=0;
for(int k=1;k<=m;k++){//最大字段和
cmx=max(b[k],cmx+b[k]);
mx=max(mx,cmx);
}
ans=max(ans,mx);
}
}
if(ans<0){
cout<<0;
}
else{
cout<<ans;
}
return 0;
}
标签:1051,51nod,ll,矩阵,int,505
From: https://www.cnblogs.com/sadlin/p/18405218