usaco-1.5.1 数字金字塔

题目描述

给定 $R$ 层数字金字塔（ $1 \le R \le 1000$ ，每个数是不大于 100 的非负整数），第 $i$ 层有 $i$ 个数。从顶部出发，每步只能走到下一层的正下方或右下方，直到最底层，求路径上数字和的最大值。

样例输入首行为 5，金字塔为 7 / 3 8 / 8 1 0 / 2 7 4 4 / 4 5 2 6 5（/ 表示换行）；输出 30（路径 $7 \to 3 \to 8 \to 7 \to 5$ ）。输出为单独一行，即最大路径和。

思路

设 $dp_j$ 表示走到当前层第 $j$ 个数的最大路径和。每个格子只能从上一层正上方或左上方两格到达，故 $dp_j = a_j + \max(dp_{j-1}, dp_j)$ ，越界的一项不存在直接忽略。自上而下逐层滚动更新，最后取末行的最大值即为答案。时间复杂度 $O(R^2)$ ，空间复杂度 $O(R)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:07
# update_at: 2026-10-01 03:11

import sys
from functools import reduce


def extend(above: list[int], row: list[int]) -> list[int]:
    """把“走到上一行为止的最大路径和”延伸到本行：每格只可能从正上方或左上方走来。

    先把上一行首尾各复制一份（`above[0]` 补在左边、`above[-1]` 补在右边），
    第 j 格的两个来源就固定是补长后的 `sources[j]` 与 `sources[j+1]`；
    越界一侧复制到的正是自己，`max` 于是等价于“该格只有一个来源”。
    """
    sources = [above[0], *above, above[-1]]
    return [v + max(sources[j], sources[j + 1]) for j, v in enumerate(row)]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    row_count = next(data)                                     # 题面的 R
    # 第 i 层恰好有 i 个数，按三角结构逐层消费 token，不依赖文件在哪里换行
    rows = (
        [next(data) for _ in range(length)]
        for length in range(1, row_count + 1)
    )
    # 自顶向下折叠：每折一层得到该层每格的最大路径和，只需保留最新一行
    print(max(reduce(extend, rows)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:32
 * update_at: 2026-10-06 09:32
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXR = 1005;

ll prev_row[MAXR]; // prev_row[j] 表示走到上一层第 j 个数的最大路径和
ll cur_row[MAXR];  // cur_row[j] 表示走到当前层第 j 个数的最大路径和

int main() {
    int R;
    if (!(cin >> R)) {
        return 0;
    }

    ll value;
    cin >> value;
    prev_row[1] = value; // 第一层只有一个数，它就是起点

    for (int i = 2; i <= R; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> value;
            // 第 j 个数只能从上一层第 j-1、j 个数走下来；不存在的来源记为 -1
            ll from_left = (j >= 2) ? prev_row[j - 1] : -1;
            ll from_up = (j <= i - 1) ? prev_row[j] : -1;
            cur_row[j] = value + max(from_left, from_up);
        }
        for (int j = 1; j <= i; j++) {
            prev_row[j] = cur_row[j];
        }
    }

    // 终点可以停在底层任意位置，答案是末行的最大值
    ll answer = prev_row[1];
    for (int j = 2; j <= R; j++) {
        answer = max(answer, prev_row[j]);
    }
    cout << answer << "\n";
    return 0;
}

usaco-1.5.1 数字金字塔

目录

题目描述

思路

参考代码