三倍经验

形式化题目

一个三角形网格, 第 $i$ 行有 $i$ 个格子, 格值 $a_{i,j}$ , 其中 $1 \leqslant i \leqslant n$ , $\lvert a_{i,j}\rvert \leqslant 10^9$ .

从 $(1,1)$ 出发, 每步从 $(i,j)$ 走到 $(i+1,j)$ 或 $(i+1,j+1)$ , 走 $n-1$ 步到达第 $n$ 行. 选一个 0/1 序列 $c_1, \dots, c_n$ 标记路径上每个格子是否翻三倍, 要求 $\sum_{i=1}^{n} c_i \leqslant k$ , 其中 $0 \leqslant k \leqslant \dfrac{n(n+1)}{2}$ .

求 $\displaystyle\sum_{i=1}^{n} a_{i,p_i} \cdot 3^{c_i}$ 的最大值, $p_i$ 是路径在第 $i$ 行经过的列号.

样例

样例是 5 行的金字塔, $k = 3$ .

text

1
2
3
4
5 7
 3  9
 8  1  0
 2  7  4  4
4  5  2  6  5

最优方案走的路径是 $7 \to 9 \to 1 \to 7 \to 5$ , 和为 $29$ . 把其中的 $7, 9, 7$ 三个数乘 $3$ , 得分变成 $21 + 27 + 1 + 21 + 5 = 75$ , 与样例输出一致.

顺带一个提醒: 路径 $7 \to 3 \to 8 \to 7 \to 5$ 的和是 $30$ , 比 $29$ 更大, 但它乘 $3$ 后最多只有三个数能翻倍, 取其中最大的 $24, 21, 21$ 得 $24 + 21 + 21 + 3 + 5 = 74$ , 反而比 $75$ 小. 所以"走哪条路径"和"哪些格子翻倍"必须同时决定, 不能分成两步贪心.

暴力解法

思路

按定义做两层枚举: 先枚举整条路径, 再枚举这条路径上每个格子乘不乘 3.

路径用递归生成: 第 row 行在第 col 列时, 往 (row+1, col) 和 (row+1, col+1) 递归.
走到第 $n$ 行后, 用 01 序列递归枚举 $c_1 \dots c_n$ , 第 dep 层决定第 dep 行路径上的格子乘不乘 3.
到叶子时累加得分, 若用掉的次数不超过 $k$ 就更新答案.

它把两层选择序列都完整生成, 覆盖所有合法方案, 因此可以作为小数据对拍的基准.

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * 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-26 13:40
 * update_at: 2026-10-26 16:36
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 递归枚举两个选择序列：每层先选"下一步走左下还是右下"，到达第 n 行后
// 再枚举路径上每个点"要不要乘 3"，检查用的次数不超过 k 后统计得分。

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

typedef long long ll;

const int MAXN = 20 + 5;

ll n, k;
ll a[MAXN][MAXN];   // 数字金字塔，a[i][j] 是第 i 行第 j 个数
ll path[MAXN];      // 路径上每一行的列号：path[i] 表示第 i 行走的列
int choose[MAXN];   // 选择序列：choose[i]=1 表示第 i 行路径上的点乘 3
ll best_ans;

// 完整路径已生成（path[1..n]），统计它在选择序列 choose 下的得分。
ll calc_answer() {
    ll used = 0;
    ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        ll j = path[i];
        ll value = a[i][j];
        if (choose[i] == 1) {
            used++;
            value = value * 3;
        }
        sum += value;
    }
    if (used <= k) {
        return sum;
    }
    return LLONG_MIN; // 超过 k 次，方案不合法
}

// 枚举路径上每个点乘不乘 3，dep 是行号。生成完整 choose[1..n] 后检查。
void dfs_choose(int dep) {
    if (dep == n + 1) {
        ll value = calc_answer();
        if (value != LLONG_MIN && value > best_ans) {
            best_ans = value;
        }
        return;
    }
    // 这一层在决定第 dep 行路径上的点要不要乘 3。
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs_choose(dep + 1);
    }
}

// 枚举从顶到底的路径：当前走到第 row 行第 col 列。
void dfs_path(int row, int col) {
    path[row] = col;
    if (row == n) {
        dfs_choose(1);
        return;
    }
    // 左下方是 (row+1, col)，右下方是 (row+1, col+1)。
    dfs_path(row + 1, col);
    dfs_path(row + 1, col + 1);
}

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

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    k = min(k, n); // 路径只有 n 个点，超过 n 的次数用不满

    best_ans = LLONG_MIN;
    dfs_path(1, 1);

    cout << best_ans << '\n';
    return 0;
}

复杂度

路径 $2^{n-1}$ 条, 每条路径 $2^{n}$ 种选择序列, 合计 $O(2^{2n})$ . 空间 $O(n)$ 递归深度.

只有 $n \leqslant 15$ 量级可用, 而题目要求 $n \leqslant 100$ .

瓶颈

瓶颈是枚举了整条路径. 同一个路径前缀在不同的选择序列下被反复重算.

再看一个更关键的浪费: 决定当前格子乘不乘 3 时, 之前具体哪些格子乘过 3 完全无关, 只需要知道已经用掉了几次. 也就是说, 整条路径上那么多格子的选择历史, 真正需要携带的只有"次数"这一个数.

正解

关键观察

把"已用次数"做成 DP 的一维, 路径前缀的最优值就和选择序列解耦了. 这个维度来自 0/1 背包, 位置维度来自数字三角形, 两者直接相乘:

dp[i][j][c] = \text{走到 } (i,j) \text{ 且恰好用了 } c \text{ 次三倍的最大得分}

转移枚举两个前驱, 每个前驱再分"当前格不乘"与"当前格乘"两种情况:

dp[i][j][c] = \max\begin{cases} \max\big(dp[i-1][j-1][c],\ dp[i-1][j][c]\big) + a_{i,j} \\[4pt] \max\big(dp[i-1][j-1][c-1],\ dp[i-1][j][c-1]\big) + 3a_{i,j}, & c \geqslant 1 \end{cases}

还有一个能省掉 $O(n)$ 倍工作量的观察: $k$ 可以截断成 $\min(k, n)$ . 一条路径通共只有 $n$ 个格子, 第 $n+1$ 次三倍机会没有格子可用, 所以 $k \geqslant n$ 与 $k = n$ 能取到的方案集合完全相同. 题面允许 $k$ 到 $\dfrac{n(n+1)}{2}$ , 不截断会白开 $n$ 倍的状态.

样例推演

用样例前 3 行算 $dp[i][j][c]$ ( $k' = \min(3, 5) = 3$ ), 行是格子、列是已用次数 $c$ . - 表示该状态不可达.

格子	$c=0$	$c=1$	$c=2$	$c=3$
$(1,1)$ 值 7	7	21	-	-
$(2,1)$ 值 3	10	24	30	-
$(2,2)$ 值 9	16	34	48	-
$(3,1)$ 值 8	18	34	48	54
$(3,2)$ 值 1	17	35	49	51
$(3,3)$ 值 0	16	34	48	48

表前看三点: 第 1 行只有 1 个格子, 所以 $c \geqslant 2$ 不可达; $c$ 相同时同一行右边的值来自不同前驱; 每格的 $c$ 越大值也越大(样例权值全为正, 但这不是普遍规律).

表后看最典型的一格 $(3,1)$ 值 8: 它的前驱只有 $(2,1)$ . $c=3$ 时两条路都是把三个格子全乘 3, $21 + 9 + 24 = 54$ , 正好等于表中 $54$ . $(2,2)$ 值 9 的 $c=2$ 是 $48$ , 来自 $(1,1)$ 的两个 $21$ 路线之一. 可见每格的每个 $c$ 都能对上一条具体路径.

思路

有了状态和转移, 剩下三处容易写错的地方要交代.

为什么用"恰好 $c$ 次"而不是"至多 $c$ 次". 恰好让转移只需看 $c-1$ 这一列, 边界清楚; 最后答案取 $\max_{j,c} dp[n][j][c]$ 即可, 因为用不满 $k$ 次是允许的.
为什么答案不能只看 $c = k'$ . 权值可以是负数, 把负数乘 3 只会更小, 所以用满次数往往不是最优. 必须遍历所有 $c$ 取最大.
哨兵要能承受加法. 不可达状态用 -inf 标记, 但 -inf + a[i][j] 会溢出, 所以要选一个足够小又不会溢出的值.

正确性由两条夹逼给出:

$dp$ 的每个取值都对应一条真实方案: 归纳, 转移的每个分支都是"前驱方案接上 $(i,j)$ 并不乘/乘 3".
任取一条最优方案, 它在 $(i,j)$ 只有"不乘"与"乘"两种情形, 分别由 DP 的两个分支覆盖; 前驱部分由归纳不超过对应的 $dp$ 值. 故方案得分不超过 $dp[i][j][c]$ .
两个方向合起来 $dp[i][j][c]$ 就是该状态的最优值.

代码

main.cpp 是正式主解. main.py 是同一算法的 Python 实现, 复杂度同阶, 放在同一节.

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * 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-26 13:40
 * update_at: 2026-10-26 16:36
 */
// main.cpp：数字金字塔 + 三倍次数的三维 DP，滚动数组实现。

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

typedef long long ll;

const int MAXN = 100 + 5;
const ll NEG_INF = LLONG_MIN / 4; // 不可达状态的哨兵，加一个格子权值也不会溢出

ll n, k;                // 行数、乘 3 次数上限（读入后截断成 k' = min(k, n)）
ll a[MAXN][MAXN];       // 数字金字塔，a[i][j] 是第 i 行第 j 个数
ll dp[2][MAXN][MAXN];   // 滚动数组：dp[cur][j][c] = 走到 (当前行, j) 且已乘 3 共 c 次的最大得分

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

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    // 一条路径只经过 n 个格子，用不完 n 次以上的乘 3 机会，截断后状态数有限。
    if (k > n) {
        k = n;
    }

    int pre = 0; // 上一行对应的层
    int cur = 1; // 当前行对应的层
    // 整张滚动数组先全部置成 NEG_INF，避免读到上一行不存在的列时拿到旧值
    for (ll i = 0; i < 2; i++) {
        for (ll j = 0; j <= n; j++) {
            for (ll c = 0; c <= k; c++) {
                dp[i][j][c] = NEG_INF;
            }
        }
    }
    dp[pre][1][0] = a[1][1]; // 起点 (1,1)，不乘 3
    if (k >= 1) {
        dp[pre][1][1] = a[1][1] * 3; // 起点乘 3
    }

    for (ll i = 2; i <= n; i++) {
        // 当前行会在第 i 列被写入，但只会读第 1..i 列，多清到 n 防止读到旧行残留
        for (ll j = 0; j <= n; j++) {
            for (ll c = 0; c <= k; c++) {
                dp[cur][j][c] = NEG_INF;
            }
        }
        for (ll j = 1; j <= i; j++) {
            for (ll c = 0; c <= k; c++) {
                // 先从两个前驱里取较大值，再加当前格的贡献
                ll best = dp[pre][j][c]; // 前驱 (i-1, j)，即从左上方下来
                if (dp[pre][j - 1][c] > best) {
                    best = dp[pre][j - 1][c]; // 前驱 (i-1, j-1)，即从右上方下来
                }
                if (best != NEG_INF) {
                    dp[cur][j][c] = best + a[i][j]; // 当前格不乘 3
                }
                if (c >= 1) {
                    // 当前格乘 3：前驱要求上一行恰好用了 c-1 次
                    ll best2 = dp[pre][j][c - 1];
                    if (dp[pre][j - 1][c - 1] > best2) {
                        best2 = dp[pre][j - 1][c - 1];
                    }
                    if (best2 != NEG_INF) {
                        if (best2 + a[i][j] * 3 > dp[cur][j][c]) {
                            dp[cur][j][c] = best2 + a[i][j] * 3;
                        }
                    }
                }
            }
        }
        swap(pre, cur); // 当前行算完，滚动到下一行
    }

    // 答案：最后一行任意一列、任意已用次数（允许用不满 k 次，dp 值随 c 非降不保证，取 max）
    ll ans = NEG_INF;
    for (ll j = 1; j <= n; j++) {
        for (ll c = 0; c <= k; c++) {
            if (dp[pre][j][c] > ans) {
                ans = dp[pre][j][c];
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

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
50
51
52
53
54
55
56
57
58#!/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-26 13:40
# update_at: 2026-10-26 13:40

import sys

NEG = None  # 哨兵：状态不可达（本行该位置到不了）


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)

    tri: list[list[int]] = []  # tri[i-1] 是第 i 行（下标 0 起）
    for i in range(n):
        tri.append([next(data) for _ in range(i + 1)])

    # 一条路径只经过 n 个格子，用不完 n 次以上的乘 3 机会
    limit = k if k < n else n

    # prev[j][c]：走到上一行第 j 列（0 起）、已乘 3 共 c 次的最大得分；NEG 表示不可达
    prev: list[list[int | None]] = [[NEG] * (limit + 1) for _ in range(n)]
    prev[0][0] = tri[0][0]
    if limit >= 1:
        prev[0][1] = tri[0][0] * 3

    for i in range(1, n):  # 第 i+1 行，本行列号 0..i
        width = limit + 1
        cur: list[list[int | None]] = [[NEG] * width for _ in range(i + 1)]
        for j in range(i + 1):
            row = cur[j]
            for c in range(width):
                # 不乘 3：前驱 (j) 与 (j-1)，各自恰好用了 c 次
                best = prev[j][c] if j < i else NEG
                left = prev[j - 1][c] if j >= 1 else NEG
                pick = best if best is not None and (left is None or best >= left) else left
                if pick is not None:
                    row[c] = pick + tri[i][j]
                # 乘 3：前驱要求上一行恰好用了 c-1 次
                if c >= 1:
                    best2 = prev[j][c - 1] if j < i else NEG
                    left2 = prev[j - 1][c - 1] if j >= 1 else NEG
                    pick2 = best2 if best2 is not None and (left2 is None or best2 >= left2) else left2
                    if pick2 is not None:
                        value = pick2 + tri[i][j] * 3
                        if row[c] is None or value > row[c]:
                            row[c] = value
        prev = cur

    reachable = [value for row in prev for value in row if value is not None]
    print(max(reachable))


if __name__ == "__main__":
    solve()

复杂度

设 $k' = \min(k, n)$ . 状态数 $O(n^2 k')$ , 每个状态常数次转移.

时间复杂度 $O(n^2 k')$ , 最坏 $k' = n$ 时为 $O(n^3)$ . $n = 100$ 时约 $10^6$ 个状态.
空间复杂度 $O(n k')$ : 第 $i$ 行只依赖第 $i-1$ 行, 滚动数组压掉一维.

总结

本题是数字三角形 DP 与 0/1 背包的组合.

关键在于认出只需要携带"已用次数"这一个历史量: 路径怎么来的、前面哪些格子乘过 3, 都不影响后续决策. 把这个量做成第三维, $2^{2n}$ 的枚举就压成了 $n^3$ .

另外两个细节决定了程序是否正确: $k$ 必须截断成 $\min(k, n)$ , 答案必须遍历所有次数取最大(因为权值可以为负, 用满次数不一定更好).

目录

形式化题目

样例

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

样例推演

思路

代码

复杂度

总结