单调队列优化 dp

Zhl2010 · 2025-07-09 17:48:07 · 算法·理论

基础概念

顾名思义，单调队列优化 dp 当然是用来优化动态规划的。

单调队列主要用于维护两端指针单调不减的区间最值。

--OI WIKI

我个人感觉单调队列优化 dp 代码不长，考场还是能写，只要你想到了，并注意了细节就行。

我们先用一道例题引入吧。

模板 1

P1440 求m区间内的最小值。

题目描述

一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0。

对于 100\% 的数据，保证 1\le m\le n\le2\times10^6，1\le a_i\le3\times10^7。

样例：

6 2
7 8 1 4 3 2

0
7
7
1
1
3 

给一点时间思考一下。

我因为实在找不到模板题，就只能选这一道当模板题了🤔。

个人认为这道题还是比较板的，它可以让你想到什么是单调队列优化 dp，然后了解它的本质。

思路

首先，我们发现这道题好像不能用动态规划，因为这道题问的是最小值。

但是，我们发现这个的时间复杂度足足 O(n^2)，过不了一点。

那么我们能不能模拟队列？

然后，我们可以想到，用一个单调队列去优化，也就是每次放一个数进去，查询时找出最小的符合条件的。

我们发现能影响一个数的只有它的时间和大小。

我们把大小更小的放前面，大小更大的但是能留的时间更长的放后面。

也就是每次更新时将比它大的所有数弹出（因为这个数能留的时间长，而且小，一定更优），然后将时间过老的弹出。

这样，我们只需要每次查询队头就行了。

来模拟一下样例：

6 2
7 8 1 4 3 2

首先，在第一次查询时，没有一个符合条件，直接输出 0。

然后：

7:
7
lr

8:  7 更小，8 能保留更久
7 8
l r

1:  将 7，8 弹出，因为 1 更小
1
lr

4：
1 4
l r

3:  1 时间过了，3 比 4 小
3 lr

然后最后一个数是 2，对任何一个查询都没有影响，直接忽略。

代码

来看一下代码，还是比较形象。

#include <bits/stdc++.h>
/*
我个人比较习惯手写队列，所以这份代码是手写的队列。
*/
#define int long long
using namespace std;
int n,m,a[2000010];
int f[2000010];//动态规划数组
int q[2000010],l=1,r=0;//手写队列
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }

    cout<<0<<endl;//第一个一定是 0
    for(int i=2; i<=n; i++) {
        while(a[q[r]]>a[i-1]&&l<=r)r--;
        /*保证这个队列是单调的，a[i] 一定要是最大的*/
        q[++r]=i-1;
        while(i-q[l]>m)l++;
        /*其实要用 if，只不过很多题都要用 while，这里也用 while 吧*/
        f[i]=a[q[l]];
    }

    for(int i=2; i<=n; i++) {
        cout<<f[i]<<endl;
    }

    return 0;
}
/*
10 5
8 5 18 12 18 12 10 7 15 1

*/

模板升级

P2034 选择数字。

题目描述

给定一行 n 个非负整数 a_1 \cdots a_n。现在你可以选择其中若干个数，但不能有超过 k 个连续的数字被选择。你的任务是使得选出的数字的和最大。

样例：

5 2
1
2
3
4
5

12

大家可以用上一道题的思路接着思考一下。

思路

这道题比较妙。

他说：不能有超过 k 个数字被选择，这个条件有一点复杂，我们可以转换一下，变成：每 k 个数必须删除 1 个数。

首先，我们很容易列出朴素 dp 式子：

设 f_{i} 表示选择 i（而且 i 会影响到旁边的距离 k 以内的数），最小的和。

当然，转移的式子：

一算复杂度：O(nm)！

然后我们发现，复杂度都是被 \min\limits_{j=i-k}^{i-1}\{f_{j}\} 撑爆的，所以我们考虑优化。

因为这是最小值，我们可以用单调队列优化。

我们在单调队列中存下距离 i 为 k 以内的数，然后每次用这个数更新。

总体跟上一题一样。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,sum=0;
int a[100010];
int f[100010];
int q[100010],l=1,r=0;
signed main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];

    q[++r]=0;
    for(int i=1;i<=n;i++){
    /*每一个 f[i] 代表 i 附近的 k 个数选了 i*/ 
        while(i-q[l]>k+1&&l<r)l++;
        f[i]=f[q[l]]+a[i];
        while(l<=r&&f[q[r]]>f[i])r--;
        q[++r]=i;
    }

    int ans=1e18;
    for(int i=n-k;i<=n;i++){
        ans=min(ans,f[i]);
    } 

    cout<<sum-ans<<endl;

    return 0;
}
/*

*/

总结 1

我们遇到这种题，需要找到要维护的最值，然后用队列维护。

我们需要维护 l，表示时间是否有效。

我们还需要维护 r，表示这个值是不是又大又新的，同样大小，一定是新的更优。

什么时候能用单调队列优化 dp 呢？

当然是 l,r 都是单调的，也就是能对当前值做出贡献的，一定不会被前面的删除。

练习题 1

P3572 [POI 2014] PTA-Little Bird。

这道题好像原本是蓝题，然后不知道为什么掉绿了。

这里就不详细讲解了，可以当作之后的练习题来做。

题目描述

有 n 棵树排成一排，第 i 棵树的高度是 d_i。

有 q 只鸟要从第 1 棵树到第 n 棵树。

当第 i 只鸟在第 j 棵树时，它可以飞到第 j+1, j+2, \cdots, j+k_i 棵树。

如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 1，否则不会。

由于这些鸟已经体力不支，所以它们想要最小化劳累值。

样例：

9
4 6 3 6 3 7 2 6 5
2
2
5

2
1

这是一道比较容易的练习题，给点时间想一下。

思路

其实这道题跟上一道题很像，只是 j+k_i 相当于在一个节点，有他前面的 k 个数对他有贡献，其他的跟上一道题差不多，就是要注意细节。

这里不多说。

代码

应该不用放了。

练习题 2

P6563 [SBCOI2020] 一直在你身旁。

前天，有学长来到我们的机房，说：这道题很厉害。

题目描述

题目描述

回到这座小镇后，她的新工作是维修电线。

现在，有一根电线坏了。已知电线长度可能为 1,2,\cdots,n 中的一个数。现在，她需要知道电线的长度。

她可以花费 a_i 块钱购买长度为 i 的电线。购买这根电线后，她能知道所需要的电线长度是否 大于 i。

保证 a_1 \le a_2 \le \cdots \le a_n \le 10^9。
问她至少要花多少钱才能保证知道需要电线的长度。