三倍经验

题意

给一个数字三角形。

从顶端走到底端，每一步只能走到左下或右下。你可以把路径上不超过 k 个数变成原来的 3 倍。

问最大路径和是多少。

思路

先看一个可以直接验证想法的朴素解：

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// brute.cpp：小数据暴力搜索，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, k;
long long a[MAXN][MAXN];
long long best_ans;

void dfs(int x, int y, int used, long long sum) {
    // 当前点不用三倍经验。
    long long sum1 = sum + a[x][y];
    if (x == n) {
        best_ans = max(best_ans, sum1);
    }
    else {
        dfs(x + 1, y, used, sum1);
        dfs(x + 1, y + 1, used, sum1);
    }

    // 当前点使用一次三倍经验。
    if (used < k) {
        long long sum2 = sum + a[x][y] * 3;
        if (x == n) {
            best_ans = max(best_ans, sum2);
        }
        else {
            dfs(x + 1, y, used + 1, sum2);
            dfs(x + 1, y + 1, used + 1, sum2);
        }
    }
}

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

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

    k = min(k, n);
    best_ans = -(1LL << 60);
    dfs(1, 1, 0, 0);

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

暴力思路是：

枚举整条从顶到底的路径
对路径上的每个点再决定“要不要三倍”

但这样分支太多，必须做 DP。

最自然的状态是：

当前走到了第几行
当前在这一行的哪个位置
已经用了多少次三倍经验

于是定义：

dp[i][j][c] 表示走到第 i 行第 j 个位置，并且已经用了 c 次三倍经验时，能得到的最大分数

当前点 (i,j) 只可能从上一行两个位置转移过来：

(i-1,j-1)
(i-1,j)

而当前点自己又有两种选择：

不使用三倍经验，贡献是 a[i][j]
使用一次三倍经验，贡献是 3 * a[i][j]

所以枚举父节点后，分别更新这两种情况即可。

DP 转移方程

设：

best=\max(dp[i-1][j-1][c],\ dp[i-1][j][c])

不使用三倍经验：

dp[i][j][c]=\max(dp[i][j][c],\ best+a[i][j])

若 c>0，使用一次三倍经验：

dp[i][j][c]=\max(dp[i][j][c],\ \max(dp[i-1][j-1][c-1],dp[i-1][j][c-1])+3a[i][j])

这里还有一个很关键的小优化：

虽然题目里的 k 可能很大，但一条合法路径从上到下只会经过 n 个点，所以真正可能用到的三倍次数不会超过 n。

因此可以先做：

k = min(k, n)

这样状态数会小很多。

再注意到第 i 行的状态只依赖第 i-1 行，所以可以用滚动数组把第一维压掉。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const long long NEG_INF = -(1LL << 60);

int n, k;
long long a[MAXN][MAXN];
long long pre[MAXN][MAXN], cur[MAXN][MAXN];

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

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

    // 一条路径一共只会经过 n 个点，所以真正有意义的三倍次数不会超过 n。
    k = min(k, n);

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            pre[i][j] = NEG_INF;
            cur[i][j] = NEG_INF;
        }
    }

    pre[1][0] = a[1][1];
    if (k >= 1) {
        pre[1][1] = a[1][1] * 3;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int c = 0; c <= k; c++) {
                cur[j][c] = NEG_INF;
            }
        }

        for (int j = 1; j <= i; j++) {
            for (int c = 0; c <= k; c++) {
                long long best = NEG_INF;

                // 当前点不使用三倍经验。
                if (j <= i - 1) {
                    best = max(best, pre[j][c]);
                }
                if (j - 1 >= 1) {
                    best = max(best, pre[j - 1][c]);
                }
                if (best != NEG_INF) {
                    cur[j][c] = max(cur[j][c], best + a[i][j]);
                }

                // 当前点使用一次三倍经验。
                if (c > 0) {
                    long long best2 = NEG_INF;
                    if (j <= i - 1) {
                        best2 = max(best2, pre[j][c - 1]);
                    }
                    if (j - 1 >= 1) {
                        best2 = max(best2, pre[j - 1][c - 1]);
                    }
                    if (best2 != NEG_INF) {
                        cur[j][c] = max(cur[j][c], best2 + a[i][j] * 3);
                    }
                }
            }
        }

        for (int j = 0; j <= i; j++) {
            for (int c = 0; c <= k; c++) {
                pre[j][c] = cur[j][c];
            }
        }
    }

    long long ans = NEG_INF;
    for (int j = 1; j <= n; j++) {
        for (int c = 0; c <= k; c++) {
            ans = max(ans, pre[j][c]);
        }
    }

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

复杂度

设实际参与 DP 的三倍次数上限为 k' = min(k, n)。

状态数大约是 $O(n^2 k')$ ，每个状态只做常数次转移。

时间复杂度 $O(n^2 k')$ ，空间复杂度 $O(n k')$ 。

在本题范围内完全可以通过。

总结

这题本质是“数字三角形”上的带次数限制 DP。

关键点有两个：

状态里要把“已经用了多少次三倍经验”记进去
k 实际上可以直接截成 min(k,n)

看出这两点后，整题就是很直接的三维 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析