「POI2014」PTA-单调队列

给定$n$个点的高度,规定从$1$点出发,跳到比高度小于当前点的点不消耗体力,否则消耗一点体力,最后到达$n$点。

$q$次询问,每次询问有一个步伐限制$k$,求最少耗费的体力。

链接

Luogu P3752

题解

很明显的一个dp。

状态转移方程:

$$
\begin{equation}
dp[i] = \min_{j \geq i-k}
\begin{cases}
dp[j] + 1 & ht[i] \geq ht[j]\\
dp[j], & ht[i] < ht[j]
\end{cases}
\end{equation}
$$

注意到$j$随$i$的变化而单调递增,所以这个东西可以用单调队列来完成$O(n)$的复杂度。

不过有一点小问题,在于这个加一的问题。我们注意到,如果我们把dp的值当作第一关键字,高度当作第二关键字,如果最优解的高度较矮,加一之后也不会比次优解要差(单调队列里的最优和次优至少差$1$),所以我们可以如此优化。

时间复杂度$O(nq)$。

代码

点击切换显示状态
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
47
48
49
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1100000;
int n,m;
int num[MAXN], dp[MAXN];
deque<int> q;// 其中的int为pos

void init(){
scanf("%d",&n);
num[0] = 0x3f3f3f3f;
for(int i = 1;i<=n;i++)
scanf("%d",&num[i]);
}
bool cmp(int x,int y){
// 1 -> x 的优先级大于y;0 -> y的优先级大于x
if(dp[x]!=dp[y])
return dp[x] < dp[y];
return num[x] > num[y];
}
int getans(int k){
dp[1] = 0;
while(!q.empty()) q.pop_back();
q.push_back(1);
for(int i = 2;i<=n;i++){
while(!q.empty() && q.front() < i-k)
q.pop_front();
dp[i] = dp[q.front()] + ((num[q.front()] > num[i])? 0: 1);
while(!q.empty() && cmp(i,q.back()))
q.pop_back();
q.push_back(i);
}
return dp[n];
}

void solve(){
scanf("%d",&m);
int t;
for(int i = 1;i<=m;i++){
scanf("%d",&t);
printf("%d\n",getans(t));
}
}

int main(){
init();
solve();
return 0;
}