题解

动态规划入门题目。

#include<bits/stdc++.h>
using namespace std;
int dp[205][205];
int main(){
	int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
    	for(int j = 1;j <= m;j ++){
            int x;
            cin >> x;
            if(i == 1){
            	dp[i][j] = x;
            } else {
        		dp[i][j] = max(max(dp[i - 1][j - 1],dp[i - 1][j]),dp[i - 1][j + 1]) + x;
            }
        }
    }
    cout << max(max(dp[n][m / 2],dp[n][m / 2 + 1]),dp[n][m / 2 + 2]);
	return 0;
}