单调队列优化DP

· · 个人记录

1.单调队列

1.1单调队列的性质

单调队列是一种特殊的双端队列，其内部元素就有单调性

设有一个长为n序列A，其元素为A_{1},A_{2}\cdots A_{n}，每个元素i都有一个优先级P_{i}

则单调队列中的元素一定是按照队列的方式，先进先出的，按照单调的方式，优先级递增或递减的（下面用递减）

则对于当前位置i，如果队列中有j(1\leq j<i)满足c[j](</\leq)c[i]，则将c[j]踢出队列，以保证单调队列的单调性

在动态规划中，单调队列要保证队列中每一个元素的下标和（动规的）状态值满足单调性（递减或递增）

由于每个元素最多出队和进队各一次，所以负责度是O(n)

可以在一定情况下，维护子区间的最值

1.2单调队列的应用

1.2.1 定长连续子序列问题

【例.1】P1886 滑动窗口 /【模板】单调队列

题目描述：

有一个长为 n 的序列a ，以及一个大小为k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

样例输入：

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

样例输出：

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

思路分析：

Window position Minnimum value Maxnimum value
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

以下分析以最小值为例，最大值同理

不难看出，对于第i个窗口来说，和第i+1个窗口有k-1个相同的数字，即有很多重复部分，可以据此来优化

维护一个单调队列

当前为第i个位置时，如果队列中有一个数a[j]，满足j<i,a[j]\geq a[i]，则a[j]是无用的，所以我们可以直接踢出单调队列，重复以上过程直到队空或者a[j]<a[i]为止

每次计算答案前需要判断队首的元素在原序列中的位置，来判断是否在结尾为i，长度为k的窗口中

将自己入队，统计答案即可

代码实现：

数组模拟队列的实现代码：

#include<cstdio>
const int maxn(1e6+5);
int n,k,h=1,t,q[maxn],a[maxn];//h表示队头，t表示队尾，q维护单调队列
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        while(h<=t&&a[q[t]]>=a[i]) t--;
        q[++t]=i;//将自己入队
        if(q[h]+k<=i) h++;//判断并踢出过期的队头
        if(i>=k) printf("%d ",a[q[h]]);
    }//求最小值
    printf("\n");
    t=0,h=1;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&a[q[t]]<=a[i]) t--;
        q[++t]=i;
        if(q[h]+k<=i) h++;
        if(i>=k) printf("%d ",a[q[h]]);
    }//求最大值
    return 0;
}

介绍一个STL：#include<deque>

q.pop_back()

q.pop_front()

q.push_back()

q.push_front()

q.front()

q.back()

q.empty()

用STL实现的单调队列

以【例.1】代码为例

#include<cstdio>
#include<deque>
const int maxn(1e6+5);
std::deque <int> q;
int n,k,a[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(!q.empty()&&q.front()+k<=i) q.pop_front();
        if(i>=k) printf("%d ",a[q.front()]); 
    }
    while(!q.empty()) q.pop_back();
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(!q.empty()&&q.front()+k<=i) q.pop_front();
        if(i>=k) printf("%d ",a[q.front()]); 
    }
    return 0;
}

【例.2】#10176. 「一本通 5.5 例 2」最大连续和

题目描述：

给你一个长度为 的整数序列{A_{1},A_{2},\cdots,A_{n}} ，要求从中找出一段连续的长度不超过m的子序列，使得这个序列的和最大。

思路分析：

进行DP，设f_(i)表示以a_{i}结尾的长度不超过m的最大子序列和

显而易见 f(i)=max\{\begin{matrix}\sum_{j=i-k+1}^i a_{i}\end{matrix}|k=1\cdots m\}

由于你优秀的时间复杂度，所以你需要去优化它

发现可以用前缀和优化，设S(i)表示前i个数的和

则f(i)=max\{S(i)-S(i-k)|k=1\cdots m\}

看出来了嘛？单调队列？

在化简一下

f(i)=S(i)-min\{S(i-k)|k=1\cdots m\}

对于min\{S(i-k)|k=1\cdots m\}，可以通过单调队列来进行维护

对于第i个值，前k个值是可以保留的（不包括自己），这不就转化成了滑动窗口吗？

用单调队列维护即可

代码实现：

#include<cstdio>
#include<deque>
const int maxn(2e5+5); 
int n,m,sum[maxn],x,ans=-2147483647;
std::deque <int> q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
    } 
    for(int i=0;i<=n;i++)
    {
        if(!q.empty()&&q.front()<i-m) q.pop_front();
        if(!q.empty()) ans=std::max(ans,sum[i]-sum[q.front()]);
        while(!q.empty()&&sum[q.back()]>=sum[i]) q.pop_back();
        q.push_back(i);
    }
    printf("%d\n",ans);
    return 0;
}
1.2.2 单调队列在DP中的常见应用

【例.3】P2627 [USACO11OPEN]Mowing the Lawn G+P2034 选择数字

双倍经验！！

题目描述：

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

思路分析：

先分析朴素DP：

设f_{i,0}表示以i结尾并且a_{i}没有被选的最大值，设f_{i,1}表示以i结尾并且a_{i}被选的最大值，

则有

f_{i,0}=max\{f_{i-1,0},f_{i-1,1}\} f_{i,1}=max\{f_{i,0}+sum_{i}-sum_{j}\}

化简一下得到

f_{i,0}=max\{f_{i-1,0},f_{i-1,1}\} f_{i,1}=sum_{i}+max\{f_{i,0}-sum_{j}\}

然后就是单调队列的板子了，不同的是，这里维护的权值是f_{i,0}-sum_{j}

代码实现：

#include<cstdio>
#include<deque> 
const int maxn(2e6+5);
int n,k;
long long sum[maxn],x,ans,f[maxn][2];
std::deque <int> q;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        sum[i]=sum[i-1]+x;
    }
    for(int i=0;i<=n;i++)
    {
        if(i) f[i][0]=std::max(f[i-1][0],f[i-1][1]);
        if(!q.empty()&&q.front()<i-k) q.pop_front();
        if(!q.empty()) f[i][1]=sum[i]-sum[q.front()]+f[q.front()][0];
        while(!q.empty()&&f[i][0]-sum[i]>f[q.back()][0]-sum[q.back()]) q.pop_back();
        q.push_back(i);
    }
    printf("%lld\n",std::max(f[n][0],f[n][1]));
    return 0;
}

后附描述：

【习.1】#10180. 「一本通 5.5 练习 1」烽火传递

【习.2】#10181. 「一本通 5.5 练习 2」绿色通道

1.2.3 单调队列优化多重背包

【例.4】P3423

题目描述：

(BBB) 拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为b_{1},b{2},\cdots，b_{n}但是每种硬币有数量限制,现在我们想要凑出面值k求最少要用多少个硬币

做法：

1.多重背包 TLE

2.二进制优化 AC

3.单调队列优化 AC

1.3 推荐习题

【习.3】P1440

【习.4】P2216

【习.5】P2569