[POI 2014] PTA-Little Bird

题意

有 n 棵树排成一排，小鸟一开始站在第 1 棵树上，目标是到达第 n 棵树。

一次可以从第 i 棵树飞到后面 k 棵之内的任意一棵树，也就是：

i+1, i+2, ..., i+k

如果这次飞行的终点高度 >= 起点高度，这一跳就算一次“疲劳跳跃”，否则不算。

对每个给定的 k，求从第 1 棵树飞到第 n 棵树时，最少需要多少次疲劳跳跃。

思路

先看一个适合小数据验证的朴素 DP：

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;

const int MAXN = 105;
const int INF = 1000000000;

int n, q_cnt;
int h[MAXN];
int dp[MAXN];

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

    // brute.cpp：朴素 DP。
    // 对每个终点 i，枚举所有能直接飞到它的起点 j。
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    cin >> q_cnt;
    while (q_cnt--) {
        int k;
        cin >> k;

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

        for (int i = 2; i <= n; i++) {
            int left = max(1, i - k);
            for (int j = left; j <= i - 1; j++) {
                int cost = dp[j];
                if (h[j] <= h[i]) {
                    cost++;
                }
                dp[i] = min(dp[i], cost);
            }
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

设 dp[i] 表示到达第 i 棵树时，最少需要多少次疲劳跳跃。

那么最直接的转移就是：

dp[i] = min(dp[j] + cost(j,i))

其中：

j 在区间 [i-k, i-1]
如果 h[j] <= h[i]，那么 cost(j,i)=1
否则 cost(j,i)=0

朴素做法每次都枚举这 k 个前驱，复杂度是 $O(nk)$ 。

正解的关键是观察：一个前驱 j 是否比另一个前驱 t 更优，只取决于两件事：

dp[j] 是否更小
当 dp 相同时，高度是否更高

为什么同样的 dp 要保留高度更高的？

因为从更高的树往后飞，更容易形成“下降跳跃”，也就是更容易让本次代价变成 0。

所以我们可以说：

dp 更小的状态一定更优
dp 相同时，高度更高的状态一定不劣

于是最近 k 棵树里的前驱就可以维护成一个单调队列：

队头始终是当前窗口内最优的前驱
新状态加入时，把队尾那些“dp 更大，或 dp 相同但高度不更高”的状态删掉

这样每个位置只会进队出队一次，每次询问都能在线性时间内完成。

具体转移时：

先把窗口左边界之外的下标弹出
用队头计算 dp[i]
再把当前 i 按上面的优先级插入队列

DP 转移方程

核心状态：

dp[i] 为到第 i 棵树最少疲劳跳跃

核心转移：

dp[i]=dp[q.front]+(h[q.front]<=h[i])

答案收束：

dp[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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int n, q_cnt;
int h[MAXN];
// dp[i]：到达第 i 棵树顶部时，最少需要多少次“疲劳跳跃”。
int dp[MAXN];
// 单调队列里存的是“可能成为最优前驱”的树编号。
int que[MAXN];

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

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

    cin >> q_cnt;
    while (q_cnt--) {
        int k;
        cin >> k;

        int head = 1, tail = 1;
        dp[1] = 0;
        que[1] = 1;

        for (int i = 2; i <= n; i++) {
            // 只能从区间 [i-k, i-1] 里的树飞过来。
            while (head <= tail && que[head] < i - k) {
                head++;
            }

            int best = que[head];
            // 如果终点高度不低于起点，这一跳就会增加一次“疲劳跳跃”。
            dp[i] = dp[best];
            if (h[best] <= h[i]) {
                dp[i]++;
            }

            // 维护一个“候选起点队列”：
            // 1. dp 更小的一定更优
            // 2. 若 dp 相同，则高度更高的更优，因为它更容易形成“不疲劳”的下降跳跃
            while (head <= tail) {
                int last = que[tail];
                if (dp[last] > dp[i] || (dp[last] == dp[i] && h[last] <= h[i])) {
                    tail--;
                } else {
                    break;
                }
            }
            que[++tail] = i;
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

复杂度

设一次询问给出的参数是 k。

每次询问中，每个下标最多进队一次、出队一次，所以时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$ 。

总结

这题的关键不是把转移式硬背成模板，而是先想清楚“什么样的前驱更值得保留”。

一旦发现比较标准只有两层：

先比 dp
再比高度

就能自然得到单调队列维护候选前驱的做法。

一图流解析

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