poj1050(动态规划+最大子矩阵和)

题目要求是输入一个N*N的矩阵，然后求出这个矩阵的最大子矩阵和，在一维空间中是求最大连续字串和，这题也算是它在二维空间里的一个扩展吧……

这个动归先求第i行第j列在这一行从1到j的最大字串和，然后，计算这个代表每行最大子串和的矩阵上的每列的最大子串和……

我就在第二个步骤出过问题，好在换了种方法过了……

还是看代码吧：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=110;
int s[maxn][maxn]={0};
int p[maxn][maxn]={0};
int i,j,k;
int flag;
int n,MAX,sum;
int max(int a,int b)
{return a>b?a:b;}
void dp()
{
p[1][1]=s[1][1];
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
p[i][j]=p[i][j-1]+s[i][j];
}
for(i=1;i<=n;++i)
{
for(j=i;j<=n;++j)
{
sum=0;
for(k=1;k<=n;++k)
{
sum+=p[k][j]-p[k][i-1];
if(sum<0) sum=0;
MAX=max(MAX,sum);
}
}
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
scanf("%d",&s[i][j]);
}
dp();
printf("%dn",MAX);
return 0;
}

最后

以上就是可靠星月最近收集整理的关于poj1050(动态规划+最大子矩阵和)的全部内容，更多相关poj1050(动态规划+最大子矩阵和)内容请搜索靠谱客的其他文章。