题意:容易理解。
分析:以后碰到这种类型的题,就要考虑把矩阵先按行来处理,再按列处理。先算出每行能够能够得到的最大值,然后按列处理即可。
代码实现:
#include<stdio.h>
#include<string.h>
int n,m;
int a[],dp[][],b[];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int i,j,res;
while(scanf("%d%d",&n,&m)!=EOF)
{
res=-;
dp[][]=;dp[][]=;
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
scanf("%d",&a[j]);
dp[j][]=max(dp[j-][],dp[j-][]);
dp[j][]=dp[j-][]+a[j];
}
b[i]=max(dp[m][],dp[m][]);
if(res<b[i])
res=b[i];
}
dp[][]=;dp[][]=;
for(i=;i<=n;i++)
{
dp[i][]=max(dp[i-][],dp[i-][]);
dp[i][]=dp[i-][]+b[i];
if(res<dp[i][])
res=dp[i][];
if(res<dp[i][])
res=dp[i][];
}
printf("%d\n",res);
}
return ;
}