洛谷 P1508 Likecloud 题解

题面

很简单的一个二维DP

f[i][j]表示最后吃到(i,j)所能获得的最大值,

那么f[i][j]=max(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+a[i][j];

注意f要初始化为负无穷大；

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[2000][2000];
int f[2000][2000];
int main()
{
    memset(f,-0x3f,sizeof(f));
    scanf("%d%d",&m,&n);
    int mid=(n+1)/2;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    f[m][mid-1]=max(0,a[m][mid-1]);
    f[m][mid]=max(0,a[m][mid]);
    f[m][mid+1]=max(0,a[m][mid+1]);
    for(int i=m-1;i>=1;i--){
        for(int j=1;j<=n;j++){
            f[i][j]=max(f[i][j],max(f[i+1][j-1],max(f[i+1][j],f[i+1][j+1]))+a[i][j]);
        }
    }
    int maxn=-1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
        maxn=max(maxn,f[i][j]);
    }
    cout<<maxn;
}