Skip to content

BZOJ - 3831. 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),可以通过本题。

代码

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