给一个n^2矩阵 求一个和最大的子矩阵
先预处理行或者列的和 然后很好的转化成一维dp
这里我的 mp[i][j] 表示i行前j个数的和
dp的过程就是 枚举列的首尾
这样 相当于把每一行当成一个数 dp求最大和 就是一个简单的问题了
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
int mp[105][105];
int main()
{
int n,a,i,j,k,tmp,ans;
while(~scanf("%d",&n))
{
memset(mp,0,sizeof mp);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a);
mp[i][j]=(a+mp[i][j-1]);
}
ans=-99999999;
for(i=1;i<=n;i++)//起始列
{
for(j=i;j<=n;j++)//结束列
{
for(tmp=0,k=1;k<=n;k++)//枚举高度
{
if(tmp<0) tmp=0;
tmp+=(mp[k][j]-mp[k][i-1]);
if(tmp>ans) ans=tmp;
}
}
}
printf("%d\n",ans);
}
return 0;
}