P1074 · OFFICIAL SOLUTION

P1074 云间飞渡官方题解

Gioush OJ · P1074 云间飞渡

【部分分：测试点 1∼31\sim 31∼3】

原题为 P3572 [POI2014] PTA-Little Bird。
对一次询问给出的 $k$ ，令 $f_i$ 表示到达第 $i$ 座高台所需的最少疲劳。起点不产生疲劳，所以 $f_1=0$ 。
到达 $i$ 之前的高台 $j$ 必须满足 $i-k\leq j<i$ 。从 $j$ 跳到 $i$ 的代价为 $[h_j\leq h_i]$ ，于是

f_i=\min_{\max(1,i-k)\leq j<i} \left(f_j+[h_j\leq h_i]\right).

枚举每个转移，单次询问时间复杂度为 $\mathcal O(n^2)$ 。

【部分分：测试点 4∼84\sim 84∼8】

转移只会访问长度至多为 $k$ 的窗口，因此没有必要枚举更早的高台。
对第 $i$ 个状态枚举

j=\max(1,i-k),\ldots,i-1

即可。一次询问的时间复杂度为 $\mathcal O(nk)$ 。

对全部询问，时间复杂度为

\mathcal O\left(n\sum_{x=1}^{q}k_x\right),

正好对应本档承诺的总工作量。

【部分分：测试点 9∼119\sim 119∼11】

观察窗口中的两个候选位置 $u,v$ 。若 $f_u<f_v$ ，那么即使从 $u$ 跳到当前高台需要增加 $1$ ，也有

f_u+1\leq f_v.

因此 DP 值更小的候选永远不会比 DP 值更大的候选差。
当 $f_u=f_v$ 时，高度更大的位置更优。因为 $h_u$ 越大，条件 $h_u\leq h_i$ 越不容易成立，额外代价不会更大。
所以窗口中的候选可以按照二元组

(f_j,-h_j)

排序，最小二元组就是当前转移的最优前驱。

使用有序多重集合保存当前窗口内的 $(f_j,-h_j,j)$ 。
计算 $f_i$ 前，删除已经离开窗口的位置 $i-k-1$ 。取集合最小元素对应的位置 $p$ ，则

f_i=f_p+[h_p\leq h_i].

再把 $(f_i,-h_i,i)$ 插入集合。每个位置插入、删除各一次。
单次询问时间复杂度为 $\mathcal O(n\log n)$ ，空间复杂度为 $\mathcal O(n)$ 。

【部分分：测试点 12∼1512\sim 1512∼15】

对每个 $k_x$ 独立运行上一档的有序集合算法。
高台高度与所有询问共用，但不同 $k_x$ 的窗口边界不同，DP 值也会随之改变，不能把一组询问的集合直接沿用到下一组。
每次重新设置 $f_1=0$ 并清空集合。总时间复杂度为 $\mathcal O(nq\log n)$ ，空间复杂度为 $\mathcal O(n)$ 。
满分只差一个问题：如何利用二元组的支配关系，把有序集合降为单调队列。

【正解】

设位置 $u$ 在位置 $v$ 之前进入队列。若

f_u>f_v,

那么 $v$ 的 DP 值更小，并且 $v$ 离开窗口更晚， $u$ 永远不可能再成为最优前驱。

若 $f_u=f_v$ 且 $h_u\leq h_v$ ，那么 $v$ 的高度不小于 $u$ ，额外代价也不会更大。同时 $v$ 存活更久，仍然可以删除 $u$ 。
因此队列从头到尾按照 $(f_j,-h_j)$ 严格递增，队首始终是窗口内的最优二元组。
计算位置 $i$ 时，先从队首删除所有下标小于 $i-k$ 的位置。
设当前队首为 $p$ ，直接计算

f_i=f_p+[h_p\leq h_i].

插入 $i$ 前，从队尾不断删除满足

f_{\operatorname{back}}>f_i

或者

f_{\operatorname{back}}=f_i,\qquad h_{\operatorname{back}}\leq h_i

的位置，最后把 $i$ 放到队尾。

每个位置只会进入队列一次，也只会从队首或队尾离开一次，所以所有队列操作的总次数为 $\mathcal O(n)$ 。
一次询问的时间复杂度为 $\mathcal O(n)$ ，全部询问的时间复杂度为 $\mathcal O(nq)$ ，空间复杂度为 $\mathcal O(n)$ 。
多组数据之间要重新读取高度序列，并在每次询问开始时重置队列与本组使用的 $f_i$ 。
队列维护的并非单独的高度或 DP 值，而是由转移式推导出的二元组顺序。

【参考代码】

1/*2 * Author:Ehundategh3 * Update:2025/7/84 * Title:P3572.cpp5 * You steal,I kill6 */7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 100001011using namespace std;12 13struct queue{14    int Head=1,Tail=0,Pos[MAXN];15    void Init(){Head=1;Tail=0;return;}16    bool Empty(){return Head>Tail;}17    void Push(int a){Pos[++Tail]=a;return;}18    int Pos_Front(){return Pos[Head];}19    int Back(){return Pos[Tail];}20    void Pop_Front(){Head++;return;}21    void Pop_Back(){Tail--;return;}22}Q;23int T,Dp[MAXN],n,Value[MAXN],q,k;24void Solve(){25    memset(Dp,0,sizeof(Dp));26    scanf("%d",&k);27    Q.Init();28    Dp[1]=0;Q.Push(1);29    for(int i=2;i<=n;i++){30        while((!Q.Empty())&&Q.Pos_Front()<i-k) Q.Pop_Front();31        if(Value[i]>=Value[Q.Pos_Front()]) Dp[i]++;32        Dp[i]+=Dp[Q.Pos_Front()];33        while((!Q.Empty())&&Dp[i]<Dp[Q.Back()]) Q.Pop_Back();34        while((!Q.Empty())&&Dp[i]==Dp[Q.Back()]&&Value[i]>=Value[Q.Back()]) Q.Pop_Back();35        Q.Push(i);36    }37    printf("%d\n",Dp[n]);38}39void Tackle(){40    scanf("%d",&n);41    for(int i=1;i<=n;i++) scanf("%d",&Value[i]);42    scanf("%d",&q);43    while(q-->0) Solve();44}45int main(){46    int c;47    scanf("%d%d",&c,&T);48    while(T-->0) Tackle();49    return 0;50}