51nod 1051 最大子矩阵和
可以用前缀和容斥优化到 \(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;
}
