单调队列优化dp

XyzL · 2020-08-25 16:50:15 · 算法·理论

前置知识：

1：基础DP

2：单调队列的运用

何为单调队列？

从字面意思上来看，无非就是有某种单调性的队列。

一般的解释是 “不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小/大的元素。”

其实本质上就是一种特殊的双端队列，一般解决类似于滑动窗口的最值问题。

那么我们应该如何去维护这样一个单挑队列呢？

如何解决？

以上题为例，

题意为给定一个序列 a ，一个长度为 k 的窗口，窗口从左至右滑动，求每个区间的大小最值。

方法1：朴素算法（暴力）

我们可以对每个区间进行直接扫描，每次枚举元素 a_x 至 元素 a_{x+k-1} 的最大值和最小值，时间复杂度为 O(nk) 。

方法2： RMQ 和线段树

熟悉数据结构的奆佬知道，显然这是个静态区间最值问题。

我们可以使用线段树等数据结构将此算法优化到 O(n log_2{n}) ,虽然在此基础上还可以进行修改，但此题的 n, k 为 1e6 ，显然会超时，这时候就可以用到我们的单调队列。

方法三： 单调队列

线段树和 ST 算法都是求任意长度区间最值的通用算法，而这题有个很重要的信息，我们每次去询问的区间长度都是固定为 k 的，且每个区间都是连续的，那么对于每两个“相邻”的区间 (L, R) 与 (L + 1, R + 1) ，都会存在以下性质：

经过观察得，两个方程都有相同的地方 ：a_{L+1}. a_{L+2}...,a_{R-1}, a_R

所以，可以得出我们在求区间 (L+1, R+1) 时，我们完全没有必要再扫描一次，只要当上一次的最值落在了 a_L 上时，我们才需要重新扫描，这样，我们的算法就得到了极大地优化。

我们以最大值为例，对于任意的 L≤i≤j≤R ，如果 a_i<a_j ，那么我们的窗口在向右滑动时，最大值永远不会移动到 a_i。因为 a_i 会比 a_j 先过期，而能用 a_i 的时候，就一定可以用 a_j。此时我们就可以不需要 a_i 了。

我们常说一句话：“奆佬 ，比我小，还比我强，我要被pop_back了。”这句话和很明显与单调队列的本质相符合。

我们可以拿此题的样例来看：

8 3
1 3 -1 -3 5 3 6 7

以最小值为例，我们将 Q 表示为单调队列，P 表示其所对应的在原列表里的序号。

1. 出现 1 。此时队中没有元素，1 进队。此时，Q={1}; P={1}。

2. 出现 3 。是否可以进队？下面基于这样一个思想: 假如把 3 放进去，如果后面 2 个数都比它大，那么 3 或许可以成为最小的。此时，Q={1,3}; P={1,2}

3. 出现 -1 。队尾元素 3 比 -1 大，那么意味着只要 -1 进队，那么 3 必定成为不了最小值，原因很明显:因为当下面 3 被框起来，那么 -1 也一定被框起来，所以 3 永远不能当最小值。所以， 3 从队尾出队。同理，1 从队尾出队。最后 -1 进队，此时 Q={-1},P={3}

4. 出现 -3 .同上面分析，-1>-3，-1 从队尾出队, -3 从队尾进队。Q={-3};P={4}。

5. 出现 5 。因为 5>-3 ，同第二条分析， 5 或许可以成为最小值，所以 5 进队。此时，Q={-3,5};P={4,5}

6. 出现 3 。 3 先与队尾的 5 比较，3<5 ，按照第 3 条的分析， 5 从队尾出队。 3 再与 -3 比较，同第二条分析，3 进队。此时，Q={-3,3};P={4,6}

7. 出现 7 。队尾元素 6 小于 7 ，7进队。此时，Q={3,6,7};P={6,7,8}。

所以，当我们将窗口 (L, R) 滑动到 (L+1, R+1) 时，若队首元素不在 (L+1, R+1) 的区间中，则删除，将 a_{R+1} 插入进单调队列中，这样便可维护出最小值。

由于每个元素进队出队只有一次，所以综合时间复杂度为O({n})。

代码：

#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

题意：

现在有连续 n(1≤n≤16,000) 块木板，编号为 1 — n ， k(1≤k≤100) 个粉刷匠，每个粉刷匠只能刷一次。第 i 个人有两种选择：一是不刷，二是必须完成长度不超过 L_i (1≤L_i≤n) 并且包含 S_i (1≤S_i≤n) 的连续的木板。每完成一个任务第 i 个人需要获得 P_i 的 (1≤P_i≤10,000) 的报酬，不同人的 S_i 是不相同的。 求如何安排能够使得所有粉刷匠的报酬总和最大？

分析：

我们可以定义 f[i][j] 代表前 i 个粉刷匠粉刷完成至多前 j 个木板的最大利益。

经观察，得状态转移有一下三种：

1. 不需要第 i 个粉刷匠，即前 i-1 个粉刷匠完成前 j 个木板的工作：f[i][j]=f[i-1][j]

2. 不需要粉刷第 j 块木板，即前 i 个粉刷匠完成前 j-1 个木板的工作：f[i][j]=f[i][j-1]

3. 前 i-1 个粉刷匠粉刷到了第 k 块木板，然后第 i 个粉刷匠从第 k+1 开始一直粉刷到第 j 个木板。

前两种状态的决策点只有一个，时间复杂度为O({n})，没有必要优化。

而第三种情况，即第 i 个粉刷匠要涂，我们可以假设我们是从 k+1 涂到 j 的，根据题意可以求出 k 的取值范围，然后状态转移的条件限制了 j 的取值范围。

我们考虑每次 j 从小到大增加的过程，j 对应的 k 的取值是一个上界不变下届递增的区间，是一个滑动窗口，那我们可以用单调队列来维护决策点 k 的最优候选。

我们又可以发现，我们在单调队列中，所维护的下标和权值均是单调的。

代码：

#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

题意：

现在有 n(1≤n≤16,000) 包干草，编号为 1 — n ，每个干草堆的宽度为 a_i ，先要按照严格的摆放（不能打乱顺序摆放，不能不摆）来建立一个高度为 h 干草堆，干草堆要使上层干草的宽度不能超过下层的宽度。

求在所有可行的方案中，h 的最大值。

分析：

首先，我们看到这道题，想到的第一个方法或许是贪心。

我们让高层尽可能的小，从后往前倒叙贪心。

但是我们可以举出个反例：

6
9 8 2 1 5 5 

如果我们按照倒叙读入的思路，贪心出来的结果为 5; 5; 1, 2, 8, 9 共三层。

但正确的结果却是 5; 5, 1, 2; 8; 9 共四层。

可以得出，此贪心的错误之处在于前面的贪心使得底层过大，难以扩展。

然后，根据抽屉原理，我们可以得到一个较为贪心的结论。

构成最优解的所有方案中，一定有一种满足底层最小，即 底层最小的方案一定可以构造出最高的层数。

通俗点来说，就是干草堆底盘越小，塔身越瘦，就可以堆的越高。

此时，我们可以去考虑动态规划。

同贪心一样，我们将 a 数组倒叙输入，求其前缀和。

我们可以定义两个数组来维护dp；

进行状态转移时，我们可以枚举出上一段的结尾 j，和再上一段的结尾 k ，先判断是否满足转移条件，然后进行最小化转移，这样我们的时间复杂度就为为 O({n^3})。

但这样的时间复杂度是远远不够的，我们可以固定 j ，可以发现在移动 j 的过程中，k 也在移动，满足一个单调性，然后我们维护一个 f[i][j] 的最小值，此时我们的时间复杂度就为为 O({n^2})。

我们可以发现一个结论，在所有合法的情况中，都有 f[i][j] ≤ f[i][j-1] 。

（本人太菜了，具体也不知道是怎么发现并严格证明的，但可以看一下matthew99巨佬的博客）

所以我们可以使用一个单调队列，维护一个最右边的前驱，再结合前缀和的单调性，左端点满足条件移动，右端点维护单调递增，得到转移点时可以直接得到答案。

所以综合时间复杂度为O({n})。

代码：

以下给出非高精代码：

#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常有以下三种现象：

1. 状态转移方程一定是取最值。

2. f[i] = Max/Min(f[j]+{A_i}+{B_i})

3. 决策点有个单调的上界或下界

单调队列优化dp是一种常见的dp优化方式，是掌握和运用斜率优化的基础，很多动态规划题目都会运用到，所以追求卓越同学一定要掌握。