简单DP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;

int a[N][N];
int f[N][N];
//f[i][j] 走到(i,j)的路径集合
//属性Max

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin>> a[i][j];

    f[1][1] = a[1][1];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + a[i][j];

    //经观察得n为偶数时,最后一层落在的点一定在n/2或n/2+1
    //而n为奇数时候,最后一层落在的点一定在n/2+1
    if(n % 2 == 0) cout << max(f[n][n / 2], f[n][n / 2 + 1]);
    else cout << f[n][n / 2 + 1];

    return 0;
}