closefrom

这题跟数字金字塔的做法类似。。

只不过数字金字塔是往两条路线搜索，这题是往三条路线搜。。。

动态方程： f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];

#include <cstdio>
using namespace std;
int m,n,mid,dp[205][205],nm[205][205];
int max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&m);
    mid=m/2+1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&nm[i][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+nm[i][j];
        }
    }
    printf("%d",max(max(dp[n][mid],dp[n][mid-1]),dp[n][mid+1]));
    return 0;
}