hdu 2845(dp基础题)

题意:容易理解。

分析:以后碰到这种类型的题,就要考虑把矩阵先按行来处理,再按列处理。先算出每行能够能够得到的最大值,然后按列处理即可。

代码实现:

#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 ;
}
上一篇:深入浅出 SpringBoot 2.x _ 10. SpringBoot 集成 JavaMail 发送邮件


下一篇:C语言面试题大汇总