又上锁妖塔

题意

锁妖塔有 n 层，第 i 层爬上去要花 h_i 的时间。

你可以使用仙术免费向上跳 1 层或 2 层，但每次跳完之后，必须先爬过至少 1 层，才能再次跳跃。

要求从地面到达第 n 层的最短时间。

思路

最直接的做法是暴力枚举每一步到底是“爬”还是“跳”。

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

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

// brute.cpp：暴力枚举每一步是爬还是跳，只适合小数据对拍。

const int MAXN = 25;
const long long INF = (1LL << 60);

int n;
int h[MAXN];

// dfs(pos, tired)
// pos   : 当前所在楼层
// tired : 1 表示刚跳过，下一步不能继续跳；0 表示当前可以跳
long long dfs(int pos, int tired) {
    if (pos == n) {
        return 0;
    }

    long long ans = INF;

    // 爬到下一层一定是合法的，爬完后就恢复成可跳状态。
    ans = min(ans, (long long)h[pos + 1] + dfs(pos + 1, 0));

    // 只有当前不疲惫时，才允许继续施法跳跃。
    if (tired == 0) {
        ans = min(ans, dfs(pos + 1, 1));
        if (pos + 2 <= n) {
            ans = min(ans, dfs(pos + 2, 1));
        }
    }

    return ans;
}

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

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

    cout << dfs(0, 0) << '\n';
    return 0;
}

brute.cpp 把当前位置和“当前能不能继续跳”一起作为搜索状态，递归尝试所有合法操作。

但这样会有大量重复搜索。例如很多不同路径都可能到达“第 i 层且当前可以跳”这个局面，后续最优答案其实是一样的。

所以关键在于把“体力状态”单独记下来。

设：

dp_rest[i]：到达第 i 层，并且当前已经休息好、可以继续跳的最小花费
dp_tired[i]：到达第 i 层，并且刚刚跳完、下一步不能再跳的最小花费

转移规则完全由题意决定：

从 dp_rest[i] 出发：
- 可以爬到 i+1，代价加上 h[i+1]
- 可以跳到 i+1 或 i+2，代价不变，但会进入疲惫状态
从 dp_tired[i] 出发：
- 只能先爬到 i+1，并恢复成可跳状态

状态表

这张表展示样例中两种状态是如何往前推进的：

楼层 `i`	`dp_rest[i]`	`dp_tired[i]`
0	`0`	`inf`
1	`3`	`0`
2	`5`	`0`
3	`1`	`3`
4	`9`	`1`
5	`5`	`1`

表中最关键的是第 3 层：先从地面跳到第 2 层，再爬第 3 层，只花 1 的时间。之后再从第 3 层跳到第 5 层，总答案就是 1。

最后答案要取 min(dp_rest[n], dp_tired[n])，因为最后一步既可能是爬到终点，也可能是跳到终点。

DP 公式

设 $rest_i$ 表示到达第 $i$ 层且已经休息好、可以继续跳时的最小花费； $tired_i$ 表示到达第 $i$ 层且刚跳完、下一步不能继续跳时的最小花费。初始化：

rest_0=0,\quad tired_0=+\infty

从 $rest_i$ 出发：

rest_{i+1}=\min(rest_{i+1},\ rest_i+h_{i+1})

tired_{i+1}=\min(tired_{i+1},\ rest_i),\quad tired_{i+2}=\min(tired_{i+2},\ rest_i)

从 $tired_i$ 出发只能先爬一层恢复：

rest_{i+1}=\min(rest_{i+1},\ tired_i+h_{i+1})

最终答案为：

\min(rest_n,\ tired_n)

公式解释：是否刚跳完会影响下一步能不能继续跳，所以要拆成 rest 和 tired 两个状态。休息好时可以爬或跳，跳后进入疲惫；疲惫时只能爬一层并恢复，最后到达终点时两种状态都合法。

代码

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

const int MAXN = 1000005;
const long long INF = (1LL << 60);

int n;
int h[MAXN];
long long dp_rest[MAXN];
long long dp_tired[MAXN];

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

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

    for (int i = 0; i <= n; i++) {
        dp_rest[i] = INF;
        dp_tired[i] = INF;
    }

    // 在地面时还没有消耗法力，因此可以直接选择跳或爬。
    dp_rest[0] = 0;

    for (int i = 0; i < n; i++) {
        // 从“已经休息好”的状态出发，可以继续爬。
        if (dp_rest[i] < INF / 2) {
            dp_rest[i + 1] = min(dp_rest[i + 1], dp_rest[i] + h[i + 1]);

            // 也可以施法跳 1 层或 2 层，跳完后会进入疲惫状态。
            dp_tired[i + 1] = min(dp_tired[i + 1], dp_rest[i]);
            if (i + 2 <= n) {
                dp_tired[i + 2] = min(dp_tired[i + 2], dp_rest[i]);
            }
        }

        // 如果刚刚跳到这一层，就必须先爬至少一层来恢复体力。
        if (dp_tired[i] < INF / 2) {
            dp_rest[i + 1] = min(dp_rest[i + 1], dp_tired[i] + h[i + 1]);
        }
    }

    cout << min(dp_rest[n], dp_tired[n]) << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

总结

这题的难点不在跳跃本身，而在“跳完后必须先爬一层”的限制。

一旦把这个限制翻译成“是否刚跳过”两个状态，整题就是非常标准的线性 DP。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析