关于单调队列优化DP的研究及其在OI中的应用

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15990701.html

Part A 单调队列

何为单调队列?

单调队列（Monotone queue ）即单调递减或单调递增的队列。

例：滑动窗口

T1

题目

对于一个长为 $N$ 的序列，求所有从左到右长为 $K$ 的区间最大值和最小值。

$N,K\leqslant 10^6$

思路

以最大值为例，维护一个从大到小的队列，从队首到队尾单调不升。

这个队列维护的是 $[i,i+k-1]$ 的值，则此时最大值为队首。

然后考虑 $[i+1, i+k]$ 区间的最大值。

上一个区间的最大值能不能用呢？

我们只需要判断当前队首的编号是否大于 $i$ 即可。

如果不大于 $i$ 就pop掉。

这里主要是运用一种思想，删掉多余的元素。

考虑两个值 $a_i,a_j$，若 $i<j$ 且 $a_i<a_j$，则 $a_i$ 是完全没有意义的。

Code

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
int dui[1000010],front,rear;
int a[1000010];

int main() {
	scanf("%d%d", &n, &k);
	for(i=1; i<=n; ++i) scanf("%d", &a[i]);
	//维护最小值 
	for(i=1; i<=k; ++i) {//第一个窗口的处理 
		while(rear && a[i]<a[dui[rear]]) --rear;
		dui[++rear]=i;
	}
	printf("%d ", a[dui[1]]);
	for(i=k+1; i<=n; ++i) {//每个窗口的处理 
		while(rear>front && a[dui[rear]]>a[i]) --rear;  
		dui[++rear]=i; //新的塞进来 
		while(dui[front]<i-k+1 && front<rear) ++front; //不合要求的弄走 
		printf("%d ", a[dui[front--]]);
	}
	printf("\n");
	memset(dui, front=rear=0, sizeof(dui));
	//维护最大值 
	for(i=1; i<=k; ++i) {
		while(rear && a[i]>a[dui[rear]]) --rear;
		dui[++rear]=i;
	}
	printf("%d ",a[dui[1]]);
	for(i=k+1; i<=n; ++i) {
		while(rear>front && a[i]>a[dui[rear]]) --rear;
		dui[++rear]=i;
		while(dui[front]<i-k+1&&front<rear) ++front;
		printf("%d ",a[dui[front--]]); 
	}
	return 0;
}

T2

题目

给出一个长为 $N$ 的序列，求长度不超过 $K$ 的连续子序列的最大和。

$N, K\leqslant 2\times 10^5$

思路

方法一：双指针

方法二：前缀和+堆优化

我们先对整个序列求一遍前缀和

我们考虑当前以位置 $r$ 结尾，则位置 $l$ 要满足什么？

1. 满足区间长度小于等于 $k$，即：$r-k+1\leqslant l\leqslant r$
2. 满足区间 $[l,r]$ 之和最大，就是 $S_r-S_{l-1}$ 最大。

先考虑如何满足条件2？

我们可以拿个小根堆来维护，那么就可以保证 $S_l$ 最小。

如何满足条件1？

每次对于小根堆的堆顶，使得其满足条件1即可。

方法三：前缀和+单调队列

让我们考虑刚刚那种方法，我们能不能把优先队列改为单调队列。

要使能用单调队列，就必须满足两个条件。

由于单调队列满足单调性，所以条件2显然可以满足。

而我们刚刚是每次对小根堆的堆顶进行条件1判断，而此时我们同样可以对单调队列的队首进行类似维护。

时间复杂度 $O(n)$。

Part B 单调队列优化dp的引入

T3

题目

求一个长为 $N$ 的序列选出任意多个数的最大和。需满足不存在连续 $M$ 个数。

$N,M\leqslant 10^5$

思路

思路一

考虑暴力做法，设 $dp_i$ 表示前 $i$ 个数选且第 $i$ 个数不选的最大和。

$$dp_i=\max_{j=i-M-1}^{i-1}(dp_j+S_{i-1}-S_j)\,\,\,(1\leqslant i\leqslant N+1)$$

答案即为：

$$ans=\max_{i=1}^{n+1} dp_j$$

Code1

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n, m, i, j, k, p; 
int a[N], dp[N], sum[N];

signed main()
{
	scanf("%lld%lld", &n, &k); 
	for(i=1; i<=n; ++i)
	{
		scanf("%lld", &a[i]); 
		sum[i]=sum[i-1]+a[i]; //求前缀和 
	}
	for(i=1; i<=n+1; ++i) //区间右端点 
		for(j=max((long long)(0), i-k-1); j<=i-1; ++j) //区间左端点 
			dp[i]=max(dp[i], dp[j]+sum[i-1]-sum[j]); //dp过程 
	printf("%lld",dp[n+1]);
	return 0;
}

思路二

我们看回刚刚的式子：

$$dp_i=\max_{j=i-M-1}^{i-1}(dp_j+S_{i-1}-S_j)\,\,\,(1\leqslant i\leqslant N+1)$$

可以变换一下:

$$dp_i=\max_{j=i-M-1}^{i-1}(dp_j-S_j)+S_{i-1}\,\,\,(1\leqslant i\leqslant N+1)$$

观察可以得到 $dp_j-S_j$ 这一段只有 $j$ 这一个变量，所以可以用单调队列来维护。

Code2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010 
struct node
{
	int x, id;
}dui[N];
int n, m, i, j, k, p; 
int a[N], dp[N], sum[N];
int front, rear;

signed main()
{
	scanf("%lld%lld", &n, &k); 
	for(i=1; i<=n; ++i)
	{
		scanf("%lld", &a[i]); 
		sum[i]=sum[i-1]+a[i]; //求前缀和 
	}
	dui[++rear].x=0; dui[rear].id=0;
	for(i=1; i<=n+1; ++i) //区间右端点 
	{
		while(front<rear && dui[front+1].id<i-k-1) ++front;
		dp[i]=max(dp[i], dp[dui[front+1].id]+sum[i-1]-sum[dui[front+1].id]);
		//求当前dp值 
		while(front<rear && dui[rear].x+sum[i]-sum[dui[rear].id]<dp[i]) --rear;
		dui[++rear].x=dp[i]; dui[rear].id=i; //把当前的值塞进队列里 
	}
	printf("%lld",dp[n+1]);
	return 0;
}

T4

题目

给定一个长为 $N$ 的序列，对其中一些数进行操作，满足所有长度为 $M$ 的连续子序列中都至少存在一个数进行过操作。

$N,M\leqslant 2\times 10^5$

思路

先把暴力dp弄出来。

设 $dp_i$ 表示前 $i$ 个数中满足对 $i$ 个数进行操作后的最少操作次数。

$$dp_i=\min_{j=i-M}^{i-1}dp_j+a_i$$

显然，对 $dp_j$ 进行单调队列维护即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
int n, m, i, j, k;
int dui[N], a[N], f[N];
int front=1, rear=1;
 
int main()
{
   	scanf("%d%d", &n, &m); 
    for(i=1; i<=n; ++i) scanf("%d", &a[i]); 
    dui[1]=0;
    for(i=1; i<=n+1; ++i)
    {
        while(rear>=front&&dui[front]<i-m) ++front;
        f[i]=a[i]+f[dui[front]];
        while(rear>=front&&f[i]<f[dui[rear]]) --rear;
        dui[++rear]=i;
    }
    printf("%d", f[n+1]);
    return 0;
}

Part C 单调队列优化dp的综合应用

T5

题目

给出一个有 $N$ 个车站的环形公路，每个车站有一定的汽油可供行驶一段距离，相邻两个车站之间也有一定距离，问从每个车站出发是否能环游一周

$N\leqslant 10^6$

思路

环形问题难搞，考虑破环成链。

破成一个长度为 $2n$ 的车站序列，让我们先考虑顺时针的情况。

让我们对汽车油量和距离分别做前缀和 $s1, s2$，如果从第 $i$ 个点出发可以回到起点，就意味着在 $[i, i+n-1]$ 的区间内，满足所有油量与距离之差的前缀和都大于等于0，即满足 $(s1_j-s1_{i-1})-(s2_j-s2_{i-1})\geqslant 0\,\,\,(j\in [i, i+n-1])$。

可是这样子不好维护，于是我们可以尝试对汽车油量与距离之差做前缀和，记为 $s$。

有了 $s$ 数组，我们就可以求区间最小值减去 $s_{i-1}$ 与0作比较，相当于做一个长度为 $n$ 的滑动窗口。

逆时针同理。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000010
int n, m, i, j, k;
int o[N], d[N], s[N<<1], ans[N];
pair<int, int>p;
deque<pair<int, int> >q;

signed main() {
	scanf("%d", &n); 
	for(i=1; i<=n; ++i) scanf("%d%d", &o[i], &d[i]); 
	for(i=1; i<=2*n; ++i) s[i]=s[i-1]+o[(i-1)%n+1]-d[(i-1)%n+1];
	for(i=1; i<=n; ++i) {
		while(!q.empty() && q.back().first>s[i]) q.pop_back();
		p.first=s[i];
		p.second=i;
		q.push_back(p);
	}
	for(i=n+1; i<=2*n; ++i) {
		ans[i-n]=q.front().first-s[i-n-1];
		while(!q.empty() && i-q.front().second+1>n) q.pop_front();
		while(!q.empty() && q.back().first>s[i]) q.pop_back();
		p.first=s[i];
		p.second=i;
		q.push_back(p);
	}
	q.clear();
	for(i=1, j=2*n; i<=2*n; ++i, --j) s[i]=s[i-1]+o[(j-1)%n+1]-d[((j-1>0 ? j-1 : n)-1)%n+1];
	for(i=1; i<=n; ++i) {
		while(!q.empty() && q.back().first>s[i]) q.pop_back();
		p.first=s[i];
		p.second=i;
		q.push_back(p);
	}
	for(i=n+1; i<=2*n; ++i) {
		ans[2*n-i+1]=max(ans[2*n-i+1], q.front().first-s[i-n-1]);
		while(!q.empty() && i-q.front().second+1>n) q.pop_front();
		while(!q.empty() && q.back().first>s[i]) q.pop_back();
		p.first=s[i];
		p.second=i;
		q.push_back(p);
	}
	for(i=1; i<=n; ++i) printf(ans[i]>=0 ? "TAK\n" : "NIE\n");
	return 0;
}

总结

这道题的思路挺巧妙的。

首先对于这类题，可以先考虑破环成链，这是这类题目的常见思考方向。

然后，我们对于题目的本质进行分析，然后可以想出差值前缀和。

最后，我们发现求最小值的过程中可以使用数据结构，即单调队列进行优化，然后就能做出此题。

T6

题目

有 $N$ 道题，每道题需要 $a_i$ 分钟来做。现在有 $t$ 分钟来做题，问最短空题段为多少。

$n\leqslant 2000 ,t\leqslant 10^8$

思路

由于最长长度和最短时间都不确定。我们可以假设其中一项确定来思考。

考虑二分答案，二分最长空题段。

假设二分当前最长空题段为 $k$，我们就可以尝试dp处理。

设 $dp_i$ 表示第 $i$ 题做，且前 $i$ 题的最长空题段小于等于 $k$ 时的最短时间，我们可以枚举上一条做了的题，即：

$$dp_i=\min_{\max(j=i-k-1, 0)}^{i-1}dp_j+a_i$$

答案我们可以在 $[n-k-1, n]$ 里枚举最后一道题的位置，时间复杂度 $O(n^2\log n)$。

显然，$\min_{\max(j=i-k-1, 0)}^{i-1}dp_j$ 可以用单调队列优化，时间复杂度 $O(n\log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 500010
int n, m, i, j, k;
int l, r, mid, ans;
int dp[N], a[N], t;
pair<int , int>p;
deque<pair<int, int> >q;

int check(int k) {
	q.clear();
	p.first=0; p.second=0;
	q.push_back(p);
	for(i=1; i<=n; ++i) {
		dp[i]=q.front().first+a[i];
		while(!q.empty() && i-q.front().second>k) q.pop_front();
		while(!q.empty() && dp[i]<=q.back().first) q.pop_back();
		p.first=dp[i];
		p.second=i;
		q.push_back(p);
	}
	ans=0x7fffffffffffffff;
	for(i=n-k-1; i<=n; ++i) ans=min(ans, dp[i]);
	return ans<=t;
}

signed main() {
	scanf("%lld%lld", &n, &t); 
	for(i=1; i<=n; ++i) scanf("%lld", &a[i]); 
	l=1, r=n;
	while(l<r) {
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld", l);
	return 0;
}

T7

题目

在一个 $a×b$ 的矩阵中找出一个 $n×n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

$2\le a,b\le 1000,n\le a,n\le b,n\le 100$

思路

显然我们可以枚举上界，则此时上下界可以确定。

那么在这种情况下，这个正方形可以为如下图中的红色区域。

那哪个红色区域是最优的呢？

这里我们可以把它看作一个二维的滑动窗口，最大最小值预处理一下即可。

枚举上下界是 $O(n)$ 的，横着扫一遍是 $O(n)$ 的，总复杂度为 $O(n^2)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define N 1010
int n, m, i, j, k;
int a, b, c, ans=0x7fffffff;
int l, r, mid;
int mn[N][N][11], mx[N][N][11];
int mxx, mnn;

signed main() {
	scanf("%d%d%d", &a, &b, &n);
	for(i=1; i<=a; ++i)
		for(j=1; j<=b; ++j)
			scanf("%d", &mx[i][j][0]), mn[i][j][0]=mx[i][j][0];
	for(i=1; i<=a; ++i)
		for(k=1; k<=10; ++k)
			for(l=1, r=l+(1<<k-1); l+(1<<k)-1<=b; ++l, ++r) {
				mn[i][l][k]=min(mn[i][l][k-1], mn[i][r][k-1]),
				            mx[i][l][k]=max(mx[i][l][k-1], mx[i][r][k-1]);
			}
	c=log2(n);
	for(i=1; i+n-1<=a; ++i)
		for(j=1; j+n-1<=b; ++j) {
			mxx=0xffffffff;
			mnn=0x7fffffff;
			for(k=i; k<=i+n-1; ++k)
				mxx=max(mxx, max(mx[k][j][c], mx[k][j+n-1-(1<<c)+1][c])),
				mnn=min(mnn, min(mn[k][j][c], mn[k][j+n-1-(1<<c)+1][c]));
			ans=min(ans, mxx-mnn);
		}
	printf("%d", ans);
	return 0;
}

T8

题目

现在已知 $T$ 天内每天股票的入价 $AP_i$，出价 $BP_i$，每天最多买 $AS_i$ 股，最多卖 $BS_i$ 股，每次交易之间至少隔 $W$ 天，任意时候手上持股数量不得超过 $MaxP$，问 $T$ 天后最多赚多少钱。

$0\leq W<T\leq 2000,1\leq\text{MaxP}\leq2000$

思路

明显的dp。

设 $dp[i][j]$ 表示第 $i$ 天持股为 $j$ 的最大钱数，首先可以从上一天或者第0天推导过来。

然后考虑买入的情况，由于我们每次由上一天推导过来，具有传递性，所以我们可以由第 $i-w-1$ 天推导过来。

假设第 $i-w-1$ 天持股数量为 $k$，那么需满足 $j-as_i\leqslant k\leqslant j-1$，转移为：

$$dp[i][j]=dp[i-w-1][k]-(j-k)\times ap_i$$

可是这样的时间复杂度达到三次方级别，于是我们对上面的式子变换一下：

$$dp[i][j]=(dp[i-w-1][k]+k\times ap_i)-j\times ap_i$$

明显，前面那一部分可以用单调队列优化。

卖出情况同理。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2010
int n, m, i, j, k;
int ap[N], bp[N], as[N], bs[N];
int dp[N][N], ans, w, mx;
pair<int, int>p;
deque<pair<int, int > >q1, q2;

signed main() {
	memset(dp, 0x80, sizeof(dp));
	scanf("%lld%lld%lld", &n, &m, &w);
	for(i=1; i<=n; ++i)
		scanf("%lld%lld%lld%lld", &ap[i], &bp[i], &as[i], &bs[i]);
	for(i=1; i<=n; ++i) {
		for(j=0; j<=m; ++j) {
			dp[i][j]=dp[i-1][j];
			if(j<=as[i]) dp[i][j]=max(dp[i][j], -j*ap[i]);
		}
		if(i<=w) continue;
		for(j=0; j<=m; ++j) {
			while(!q1.empty() && q1.front().second<j-as[i]) q1.pop_front();
			while(!q1.empty() && q1.back().first<=dp[i-w-1][j-1]+(j-1)*ap[i]) q1.pop_back();
			p.first=dp[i-w-1][j-1]+(j-1)*ap[i];
			p.second=j-1;
			q1.push_back(p);
			dp[i][j]=max(dp[i][j], q1.front().first-j*ap[i]);
		}
		for(j=m; j>=0; --j) {
			while(!q2.empty() && q2.front().second>j+bs[i]) q2.pop_front();
			while(!q2.empty() && q2.back().first<=dp[i-w-1][j+1]+(j+1)*bp[i]) q2.pop_back();
			p.first=dp[i-w-1][j+1]+(j+1)*bp[i];
			p.second=j+1;
			q2.push_back(p);
			dp[i][j]=max(dp[i][j], q2.front().first-j*bp[i]);
		}
		q1.clear();
		q2.clear();
	}
	for(i=0; i<=m; ++i) ans=max(ans, dp[n][i]);
	printf("%lld", ans);
	return 0;
}

总结

这是一道非常经典的dp加单调队列优化。

dp方面，传递性的思想很巧妙。

有些时候，dp式子需要进行一定变换才能使用单调队列优化。

T9

题目

有 $n$ 种面值的硬币，分别为 $b_1, b_2,\cdots , b_n$ 。要凑出面值 $k$，最少要用多少个硬币。

$n\leqslant 2000,k\leqslant 2\times 10^4$

思路

单调队列做法略。主要是我没想懂，这里介绍一种二进制做法。

单调队列做法留给读者自己探究。

这题我本来不想写的，但是由于在老师布置的题单上，就写了另一种做法。

首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。

同时，我们也可以把每种面值的货币拆成 $c_i$ 个，用01背包求解。时间复杂度为 $O(nm^2)$。

这时我们可以考虑每种面值。设 $t=log_2c_i$，对于 $c_i$ 以内的任何一个数，我们都可以用 $2^0, 2^1,\cdots,2^t$ 凑出，所以我们并不需要把每种面值的硬币拆成 $c_i$ 份，拆成 $log_2c_i$ 份即可。

时间复杂度 $O(nm\log m)$。

这是一道经典的多重背包优化题目。

对于多重背包来说，数量的个数限制往往可以用二进制的方法组合表示。

如果一道多重背包的题能拆成01背包，那么它必然可以用二进制的方法进行优化，这是一种常见题型。

Part D 结语

最后，我想以今日英才的一段激励语来结束这篇文章。

人最宝贵的是生命，人的生命只有一次。人的一生应当这样度过：当他回首往事时，他不会因为虚度年华而悔恨;也不会因为生活的庸俗而羞愧;临死的时候，他能够说，我把我的整个生命和全部精力，都献给了全中国最辉煌的事业——OI事业，为中国在21世纪成为世界第一OI强国而奋斗和努力!

让我们用这段光彩夺目的话来鞭策和激励自己!

让自己成为一个无愧于时代的高尚的人!

谢谢您们！

没错，这段是我抄的