13 lines
687 B
Markdown
13 lines
687 B
Markdown
# P3572 [POI 2014] PTA-Little Bird 题解
|
|
|
|
$n$ 棵有高度的树。有鸟要从第 $1$ 棵树到第 $n$ 棵树。当第 $i$ 只鸟每次最多向前 $k$ 棵树。如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 $1$，否则不会。最小化劳累值。
|
|
|
|
朴素做法为设 $f_x$ 为这只鸟飞到 $x$ 的最小劳累值。则：
|
|
|
|
$$f_x = \min(f_i + (a_x >= a_i)), i \in [x - k, x - 1]$$
|
|
|
|
但这样是 $O(n^2q)$ 的，无法通过。
|
|
|
|
注意到 $f_x$ 只会由 $f_i, i \in [x - k, x - 1]$ 转移得到，且不会选择其中值过大的。考虑使用单调队列维护滑动窗口，记录可能产生贡献的值。
|
|
|
|
[code](../P3572.cpp) |