P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r;
    cin >> r;
    vector<vector<int>> a(r, vector<int>(r, 0));
    for (int i = 0; i < r; i++)
        for (int j = 0; j <= i; j++)
            cin >> a[i][j];

    // f[i][j]：从塔尖走到第 i 行第 j 列的最大路径和
    vector<vector<int>> f(r, vector<int>(r, 0));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j <= i; j++) {
            int best = 0;
            if (i > 0) best = f[i - 1][j];
            if (j > 0) best = max(best, f[i - 1][j - 1]);
            f[i][j] = best + a[i][j];
        }
    }

    int ans = 0;
    for (int j = 0; j < r; j++) ans = max(ans, f[r - 1][j]);
    cout << ans << "\n";
    return 0;
}