前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式,在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ(那年的T4考到了单调队列),当时还不会,在考后听教练讲了一遍之后仍旧处于懵逼状态,大概1个月前照着题解打了一遍,但是到了现在已经忘得差不多了QwQ,于是写了一遍优化过的多重背包来练练手。

定义

普及考完之后,我问Sooke大仙(如果T4开了longlong他就AK了)T4的做法,他跟我说:单调队列

我:(懵逼)单调队列是个啥子玩意儿

Sooke:

单调队列是一个队列,它具有单调性

是不是还是听不懂?那么我解释一下。

单调队列是一个队列(这不是废话吗QwQ),它里面的元素满足一个性质:

对于$i<j$,一定满足$v_i < v_j$ 并且 $k_i < k_j$(v为一个点的DP值, k为点在DP数组中的位置)

这就是单调队列(你问它跟DP有设么关系?看下面的吧QwQ)

用法

对于一个单调队列,你会发现如果一个要队中状态无法更关心当前扫到的这个状态,那么它也无法更新后面扫到的状态,(这个很容易证明)那么我们可以把这个状态丢掉,在通过这是最优的状态(队首元素)更新当前状态之后,将当前的状态加入队列然后继续往下扫

综上所述,一个比较精简的单调队列程序的核心部分就应该长成这样(伪代码):

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++){
while(当前状态无用)
qf++;
while(如果加入当前状态会使队列不满足单调性)
qe--;
q[++qe] = 当前状态;
if(q[qf] 更优于 f[i])
更新f[i];
}

例题

洛谷P3957 NOIP2017普及组T4 跳房子

我们看到这题之后,我们马上可以想到二分答案,在二分答案的Check()中可以加上一个DP

这题显然对于一个机器人的状态,它可以更新一个范围,所以大力套上单调队列即可

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int di[500100];
int xi[500100];
long long f[500100];
int n;
int q[1000100];
int qf, qe;
long long k;

void Push(int x){
while(f[q[qe]] <= f[x] && qe >= qf)
qe--;
q[++qe] = x;
}

long long check(int Min, int Max){
for(int i = 1; i <= n; i++)
f[i] = -1000000000000000000;
f[0] = 0;
qf = 1;
qe = 0;
int kk = 0;
q[1] = 0;
for(int i = 1; i <= n; i++){
while(di[i] - di[kk] >= Min && kk < i)
Push(kk++);
while(di[i] - di[q[qf]] > Max && qf <= qe)
qf++; // 把不符合区间的给出队
if(qf > qe || f[q[qf]] == -1000000000000000000)
continue;
f[i] = f[q[qf]] + xi[i];
if(f[i] >= k)
return true;
}
return false;
}

inline void fopen(){
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
}

int main(){
//fopen();
//freopen("jump10.in", "r", stdin);
di[0] = 0;
long long d;
scanf("%d %d %lld", &n, &d, &k);
int maxd = 0;
long long sumx = 0;
for(int i = 1; i <= n; i++){
scanf("%d %d", &di[i], &xi[i]);
if(xi[i] > 0)
sumx += xi[i];
if(di[i] > maxd)
maxd = di[i];
}
if(sumx < k){
printf("-1");
return 0;
}
int l = 0, r = maxd;
while(l < r){
int mid = (l+r) / 2;
if(check((d - mid > 1 ? d - mid : 1), d+mid))
r = mid;
else
l = mid + 1;
}
printf("%d", l);
return 0;
}

 评论