前言
单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式，在一个点可以更新一个范围的时候可以发挥很大作用。
记得当年NOIp2017我考PJ（那年的T4考到了单调队列），当时还不会，在考后听教练讲了一遍之后仍旧处于懵逼状态，大概1个月前照着题解打了一遍，但是到了现在已经忘得差不多了QwQ，于是写了一遍优化过的多重背包来练练手。
定义
普及考完之后，我问Sooke大仙（如果T4开了longlong他就AK了）T4的做法，他跟我说：单调队列
我：（懵逼）单调队列是个啥子玩意儿
Sooke：
单调队列是一个队列，它具有单调性
是不是还是听不懂？那么我解释一下。
单调队列是一个队列（这不是废话吗QwQ），它里面的元素满足一个性质：
对于i<j，一定满足vi<vj 并且 ki<kj（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(){
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;
}
|
