题解 P1508 【Likecloud-吃、吃、吃】
hicc0305
2017-07-17 15:52:35
一道简单的矩阵dp题目，用dp[i][j]存储到i，j这个点的最大值，从下到上递推出第一列的最大值，在比较一下就可以了
转移方程见程序，注意一些地方是死角，走不到，不用加进去。（PS：不知为什么数组开201,201过不了……多开一点才过）
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[401][401];
int dp[401][401];
int main()
{
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=m+1;i>=2;i--)//从最后一行的下一列开始
{
int l=n/2+1-(m-i+1),r=n/2+1+(m-i+1);//要枚举j左右值，也就把走不到的地方排出了
for(int j=max(l,1);j<=min(r,n);j++)
{
dp[i-1][j-1]=max(dp[i-1][j-1],dp[i][j]+a[i-1][j-1]);
dp[i-1][j]=max(dp[i-1][j],dp[i][j]+a[i-1][j]);
dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]+a[i-1][j+1]);//转移方程，可能有点麻烦，但不用脑子
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dp[1][i]);//比较求最值
printf("%d",ans);
return 0;
}
```