【题解】洛谷P1508 Likecloud-吃、吃、吃 线性DP
设 表示走到第 行第 列所能得到的最大能量值。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[210][210],m,n,dp[210][210];
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(dp,0xcf,sizeof(dp));
dp[m+1][(n+1)/2]=0;
for(int i=m;i;i--)
for(int j=1;j<=n;j++)
{
if(j>1)dp[i][j]=max(dp[i][j],dp[i+1][j-1]+a[i][j]);
if(j<n)dp[i][j]=max(dp[i][j],dp[i+1][j+1]+a[i][j]);
dp[i][j]=max(dp[i][j],dp[i+1][j]+a[i][j]);
}
int ans=-0x3f3f3f3f;
for(int j=1;j<=n;j++)
ans=max(ans,dp[1][j]);
printf("%d\n",ans);
return 0;
}
总结
无