单调队列优化dp
前置知识:
1:基础DP
2:单调队列的运用
何为单调队列?
从字面意思上来看,无非就是有某种单调性的队列。
一般的解释是 “不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小/大的元素。”
其实本质上就是一种特殊的双端队列,一般解决类似于滑动窗口的最值问题。
那么我们应该如何去维护这样一个单挑队列呢?
如何解决?
以上题为例,
题意为给定一个序列
方法1:朴素算法(暴力)
我们可以对每个区间进行直接扫描,每次枚举元素
方法2: RMQ 和线段树
熟悉数据结构的奆佬知道,显然这是个静态区间最值问题。
我们可以使用线段树等数据结构将此算法优化到
方法三: 单调队列
线段树和
经过观察得,两个方程都有相同的地方 :
所以,可以得出我们在求区间
我们以最大值为例,对于任意的
我们常说一句话:“奆佬 ,比我小,还比我强,我要被pop_back了。”这句话和很明显与单调队列的本质相符合。
我们可以拿此题的样例来看:
8 3
1 3 -1 -3 5 3 6 7
以最小值为例,我们将
-
出现
1 。此时队中没有元素,1 进队。此时,Q={1}; P={1} 。 -
出现
3 。是否可以进队?下面基于这样一个思想: 假如把3 放进去,如果后面2 个数都比它大,那么3 或许可以成为最小的。此时,Q={1,3}; P={1,2} -
出现
-1 。队尾元素3 比-1 大,那么意味着只要-1 进队,那么3 必定成为不了最小值,原因很明显:因为当下面3 被框起来,那么-1 也一定被框起来,所以3 永远不能当最小值。所以,3 从队尾出队。同理,1 从队尾出队。最后-1 进队,此时Q={-1},P={3} -
出现
-3 .同上面分析,-1>-3 ,-1 从队尾出队,-3 从队尾进队。Q={-3};P={4} 。 -
出现
5 。因为5>-3 ,同第二条分析,5 或许可以成为最小值,所以5 进队。此时,Q={-3,5};P={4,5} -
出现
3 。3 先与队尾的5 比较,3<5 ,按照第3 条的分析,5 从队尾出队。3 再与-3 比较,同第二条分析,3 进队。此时,Q={-3,3};P={4,6} -
出现
7 。队尾元素6 小于7 ,7 进队。此时,Q={3,6,7};P={6,7,8} 。
所以,当我们将窗口
由于每个元素进队出队只有一次,所以综合时间复杂度为
代码:
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 1 * 1e6 + 1;
int n, k, l, r, a[Maxn], q[Maxn];
int main() {
n = read(), k = read();
for(register int i = 1; i <= n; ++i) {
a[i] = read();
}
l = 1, r = 0;
for(register int i = 1; i <= n; ++i) { //最小值
while(l <= r && a[q[r]] >= a[i]) {
--r;
}
q[++r] = i;
while(q[l] + k - 1 < i) {
++l;
}
if(i >= k) {
printf("%d ", a[q[l]]);
}
}
puts("");
l = 1, r = 0;
for(register int i = 1; i <= n; ++i) { //最大值
while(l <= r && a[q[r]] <= a[i]) {
--r;
}
q[++r] = i;
while(q[l] + k - 1 < i) {
++l;
}
if(i >= k) {
printf("%d ", a[q[l]]);
}
}
puts("");
return 0;
}
如何应用?
POJ1821 Fence
题意:
现在有连续
分析:
我们可以定义
经观察,得状态转移有一下三种:
-
不需要第
i 个粉刷匠,即前i-1 个粉刷匠完成前j 个木板的工作:f[i][j]=f[i-1][j] -
不需要粉刷第
j 块木板,即前i 个粉刷匠完成前j-1 个木板的工作:f[i][j]=f[i][j-1] -
前
i-1 个粉刷匠粉刷到了第k 块木板,然后第i 个粉刷匠从第k+1 开始一直粉刷到第j 个木板。
前两种状态的决策点只有一个,时间复杂度为
而第三种情况,即第
我们考虑每次
我们又可以发现,我们在单调队列中,所维护的下标和权值均是单调的。
代码:
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 16061;
const int Maxk = 161;
int n, m, f[Maxk][Maxn], q[Maxn];
struct Node {
int l;
int p;
int s;
} a[Maxk];
inline bool Cmp(Node a, Node b) { // 计算单调队列要维护的值
return a.s < b.s;
}
inline int Calc(int i, int k) {
return f[i - 1][k] - a[i].p * k;
}
int main() {
n = read(), m = read(); // f[i][j]表示前i号工匠粉刷前j块木板的最大收入
for(register int i = 1; i <= m; ++i) {
a[i].l = read(), a[i].p = read(), a[i].s = read();
}
sort(a + 1, a + m + 1, Cmp);
for(register int i = 1; i <= m; ++i) { // 工匠
int l = 1, r = 0; // 初始化单调队列
for(register int k = max(0, a[i].s - a[i].l); k <= a[i].s - 1; ++k) { // 把可能的决策点插入deque
while(l <= r && Calc(i, q[r]) <= Calc(i, k)) { // 剔除队尾不合法的元素
r--;
}
q[++r] = k; // 当前状态k插入队尾
}
for(register int j = 1; j <= n; ++j) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]); // i木匠不粉刷,或 j木板不粉刷
// 粉刷第k+1~j块木板时的转移
if(j >= a[i].s) { // j比s大粉刷才合法,必须包括s
while(l <= r && q[l] < j - a[i].l) { //队首 < 当前下标j - 粉刷距离L,不合法的决策点
l++;
}
if(l <= r) { // 队列非空时,利用队首转移
f[i][j] = max(f[i][j], Calc(i, q[l]) + a[i].p * j);
}
}
}
}
printf("%d\n", f[m][n]);
return 0;
}
LG4954 Tower of Hay G
题意:
现在有
求在所有可行的方案中,
分析:
首先,我们看到这道题,想到的第一个方法或许是贪心。
我们让高层尽可能的小,从后往前倒叙贪心。
但是我们可以举出个反例:
6
9 8 2 1 5 5
如果我们按照倒叙读入的思路,贪心出来的结果为
但正确的结果却是
可以得出,此贪心的错误之处在于前面的贪心使得底层过大,难以扩展。
然后,根据抽屉原理,我们可以得到一个较为贪心的结论。
构成最优解的所有方案中,一定有一种满足底层最小,即 底层最小的方案一定可以构造出最高的层数。
通俗点来说,就是干草堆底盘越小,塔身越瘦,就可以堆的越高。
此时,我们可以去考虑动态规划。
同贪心一样,我们将
我们可以定义两个数组来维护dp;
进行状态转移时,我们可以枚举出上一段的结尾
但这样的时间复杂度是远远不够的,我们可以固定
我们可以发现一个结论,在所有合法的情况中,都有
(本人太菜了,具体也不知道是怎么发现并严格证明的,但可以看一下matthew99巨佬的博客)
所以我们可以使用一个单调队列,维护一个最右边的前驱,再结合前缀和的单调性,左端点满足条件移动,右端点维护单调递增,得到转移点时可以直接得到答案。
所以综合时间复杂度为
代码:
以下给出非高精代码:
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 500005;
int n, tpye;
long long a[Maxn], sum[Maxn], q[Maxn], l[Maxn], w[Maxn];
unsigned long long f[Maxn];
inline long long Calc(register int x) { // 计算单调队列要维护的值
return sum[x] + w[x];
}
int main() {
n = read(), tpye = read();
if(!tpye) {
for(register int i = 1; i <= n; ++i) {
a[i] = read();
}
}
for(register int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
}
int l = 1, r = 0; // 初始化单调队列
for(register int i = 1; i <= n; ++i) {
while(l <= r && sum[i] - sum[q[l]] >= w[q[l]]) {
++l;
}
w[i] = sum[i] - sum[q[l - 1]];
f[i] = f[q[l - 1]] + w[i] * w[i]; //状态转移
while(l <= r && Calc(i) <= Calc(q[r])) { // // 把可能的决策点插入调队列
r--;
}
q[++r] = i;
}
printf("%lld\n", f[n]);
return 0;
}
总结:
单调队列的单调是指数组下标的单调及所维护的权值的单调。
一般情况下,碰到单调队列优化dp常有以下三种现象:
-
状态转移方程一定是取最值。
-
f[i] = Max/Min(f[j]+{A_i}+{B_i}) -
决策点有个单调的上界或下界
单调队列优化dp是一种常见的dp优化方式,是掌握和运用斜率优化的基础,很多动态规划题目都会运用到,所以追求卓越同学一定要掌握。