Skip to content

「POI2014」Little Bird

题解690 字
# 洛谷 # BZOJ # 动态规划 # POI # 2014 # 单调队列 # 单调队列优化 DP
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

森林中有 nn 棵树在一条直线上，每棵树有不同的高度。小鸟从第一课树开始跳跃到最后一棵树。如果跳到比当前树矮的，小鸟不会消耗任何体力，但如果跳到的树的高度大于等于当前树的高度，则需要消耗一个体力。

小鸟准备多次不同的尝试，规定了每次的最长跳跃幅度，请求出每次的最少耗费体力值。

#输入格式

第一行一个整数 nn，表示树的数量。

第二行 nn 个整数，第 ii 个数为 did_i，表示第 ii 棵树的高度。

第三行一个整数 qq，表示本轮小鸟的步幅限制。

接下来 qq 行，每行一个整数 kik_i，表示小鸟的最少耗费的体力值。

#输出格式

对于每次尝试，输出一行一个整数，表示小鸟的最少耗费体力值。

#输入输出样例

样例输入 #1

9
4 6 3 6 3 7 2 6 5
2
2
5

样例输出 #1

2
1

#数据范围与约定

对于 100%100\% 的数据，2≤n≤1062 \leq n \leq 10^6，1≤di≤1091 \leq d_i \leq 10^9，1≤q≤251 \leq q \leq 25，1≤ki≤n−11 \leq k_i \leq n - 1。

#思路

设 fif_i 表示从起点飞行到 ii 的体力值，易得以下转移方程：

fi=min⁡j=i−ki−1(fj+[dj≤di])(1)\tag{1} f_i = \min_{j = i - k}^{i - 1}(f_j + [d_j \leq d_i])

时间复杂度为 O(qn2)O(qn^2)，无法通过本题。

考虑优化。可以发现对于每个 ii 都会去遍历一遍 fi−k∼i−1f_{i - k \sim i - 1}，因此可以用单调队列来优化。使用单调队列维护到达前面 kk 棵树的劳累值最小值（如劳累值相同则取高度最高的放在前面）。

容易证明这种做法是正确的。时间复杂度为 O(qn)O(qn)，可以通过本题。

#代码

C++
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
#include <iostream>
#include <deque>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1000005;

int n, q, k, d[N];

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

    cin >> n;

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

    cin >> q;

    while (q--) {
        cin >> k;

        std::vector<int> f(n + 1);
        std::deque<int> q;

        q.push_back(1);
        for (int i = 2; i <= n; i++) {
            while (!q.empty() && q.front() < i - k) q.pop_front();
            f[i] = f[q.front()] + (d[q.front()] <= d[i]);
            while (!q.empty()
                   && (f[q.back()] > f[i]
                       || f[q.back()] == f[i] && d[q.back()] <= d[i]))
                q.pop_back();
            q.push_back(i);
        }

        cout << f[n] << endl;
    }

    return 0;
}