dp+矩阵压缩
将二维矩阵压缩成一维,然后进行状态转移
f[i]=max(f[i-1]+s[i],s[i]);
f[i]表示以s[i]为序列右端点的,最大区间和
s[i]表示区间序列,如2 -4 3 -1 2 -4 3就是一个序列
这是一维的状态表示
对于二维的矩阵如何进行状态表示呢?
将二维矩阵压缩成一维进行状态转移:
将g[i][j]预处理成第j列的前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
g[i][j]+=g[i-1][j];
}
那么g[i][j]-g[i-k][j]
就是对于第j列的,以第i行为最后一行,往上数k行的前缀和
这样,我们通过两层循环,首先枚举最后一行,以第i行为最后一行,然后枚举k。
最后,枚举的j就是在一维状态下的状态转移了
f[k]=g[i][k]-g[i-j][k];
dp[k]=max(dp[k-1]+f[k],f[k]);
AC代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 150, M =100001;
int n,m,k;
int f[N][N];
int g[N][N],s[N][N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{ cin>>g[i][j]; g[i][j]+=g[i-1][j] ;}
int ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
int f[150]={0},dp[150]={0};
for(int k=1;k<=n;k++)
{
f[k]=g[i][k]-g[i-j][k];
dp[k]=max(dp[k-1]+f[k],f[k]);
ans=max(ans,dp[k]);
}
}
}
cout<<ans<<endl;
return 0;
}