[算法学习笔记][刷题笔记] 单调队列优化 dp
前置知识 · 单调队列
单调队列顾名思义，一般用于解决 滑动RMQ问题。它的原理非常简单。我们维护一个双端队列，这个双端队列 只维护可能成为区间最值的元素。
最基础的单调队列，例如滑动窗口。直接依据题意维护即可。
这里提供单调队列模板（STL deque 版）
单调队列模板（STL deque 版）
for(int i=1;i<=n;i++)
{
if(!q1.empty()&&i-q1.front() >= k) q1.pop_front(); //越界“退役”
while(!q1.empty()&&a[q1.back()] > a[i]) //比当前元素大， 不可能成为区间最小值。直接pop
{
q1.pop_back();
}
q1.push_back(i);
if(i>=k) cout<<a[q1.front()]<<" "; //依据题意输出答案即可，不同题目处理不同。
}
单调队列具体内容见：SXqwq的单调队列学习笔记
单调队列优化 dp
单调队列优化 dp，往往是将朴素 dp 方程转换成可以用单调队列维护的形式。这里给出几个例题。
例题1：Luogu P1714 切蛋糕
在数列 \(\{p_n\}\) 中，找出一个子段 \([l,r](r-l+1\le m)\)，最大化 \(\sum\limits_{i=l}^rp_i\)。
Solution
此类问题属于最大不定长字段和问题。
朴素做法是对于每一个 \(l\)，枚举长度，时间复杂度 \(O(n^2)\)，无法接受。
如果我们预处理 \(sum_i\) 表示数组前 \(i\) 项的前缀和，则\(max(\sum\limits_{i=l}^rp_i)=max(sum_r)-min(sum_l)(r > l)\)
对于每次处理 \(sum_r\) 固定，也就是求 \(r\) 前面最小的 \(sum_l\)。我们知道单调队列用于位于区间最值，排除无用决策。所以我们可以用单调队列维护区间长为 \(k\) 的最小 \(sum_l\)。
至此，我们就可以将本题使用单调队列维护，由于每个元素只会入队出队一次，时间复杂度 \(O(n)\) 。
实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 1000010;
int sum[N];
int n,m;
deque <int> q;
int maxn = -1;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
sum[i] = sum[i-1] + a;
}
q.push_back(0);
for(int i=1;i<=n;i++)
{
if(q.size() && i - q.front() > m) q.pop_front();
while(q.size()&&sum[q.back()] > sum[i]) q.pop_back();
maxn = max(maxn,sum[i]-sum[q.front()]);
q.push_back(i);
}
cout<<maxn<<endl;
return 0;
}
例题2：Luogu P2629 好消息，坏消息
题目链接：Luogu P2629
Solution
首先，本题存在环，直接断环成链。处理更加方便。
因为在任何时候老板的心情不能小于0，初始心情为0，所以任何时候位置 \(i\) 的前缀和不能小于0（断环为链后）。同理设 \(sum_i\) 表示前 \(i\) 个 数的前缀和。
接下来，我们就将题目转化为：求有多少个 \(k\) 满足 \(\forall sum_i \geq sum_k(i \in \{1,n\times 2\})\) (显然这里已经断环为链)
那么如何处理呢？我们需要对于每个 \(i\) 都判断一遍吗？显然不需要，因为中间哪怕出现一个小于 \(0\) 的数，就不合法。所以我们使用单调队列维护一个最小的 \(sum_i\) 即可。
需要注意我们每次需要维护区间 \([k,n+k-1]\) 的最小值，然后判断 \(sum_i-sum_k\) 是否小于 \(0\) 即可。
实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 100000010;
int n,m;
int sum[N];
int ans[N];
int a[N];
deque <int> q;
int cnt = 0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n] = a[i];
sum[i] = sum[i-1] + a[i];
}
for(int i=n+1;i<=n*2-1;i++) sum[i] = sum[i-1] + a[i];
q.push_back(1);
for(int i=2;i<=n*2-1;i++)
{
while(q.size() && sum[i] < sum[q.back()]) q.pop_back();
q.push_back(i);
while(q.size() && i - q.front() > n) q.pop_front(); //超过 n，即开始统计答案，越界。
if(i >= n) {ans[i] = sum[q.front()] - sum[i-n];}
}
for(int i=n;i<=n*2-1;i++) if(ans[i] >= 0) cnt++;
cout<<cnt<<endl;
return 0;
}