【普及组】

多维动态规划

P1508 Likecloud-吃、吃、吃

因为每行状态只影响下一行，故可以直接更改a。注意不能只选眼前三个选项中最大的，整个路线都要考虑，所以每个位置都要dp。敲代码之前反复学习题面&样例的重要性。

#include <iostream>
using namespace std;
int a[1005][1005],n,m;
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=max(a[i-1][j-1],max(a[i-1][j],a[i-1][j+1]));
        }
    }
    cout<<max(a[n][m/2],max(a[n][m/2+1],a[n][m/2+2]));
    return 0;
}