Skip to content

「POI2014」Little Bird

检测到 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\% 的数据,2n1062 \leq n \leq 10^61di1091 \leq d_i \leq 10^91q251 \leq q \leq 251kin11 \leq k_i \leq n - 1

#思路

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

fi=minj=iki1(fj+[djdi])(1)\tag{1} f_i = \min_{j = i - k}^{i - 1}(f_j + [d_j \leq d_i])

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

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

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

#代码

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;
}