浅谈单调队列及优化DP

  • Post author:
  • Post category:其他

概念

单调队列是一个满足内部单调递增或单调递减的数据结构。

实质

单调队列是一个 双端队列

特点

  • 从队尾入列,队首或队尾出列。
  • 队列中元素大小必须是 单调 的。
  • 队列中的元素对应在原来列表中的顺序必须是 单调递增 的。

作用

维护区间最值或降低 DP 维数来达到减少空间及时间的目的。

例题

洛谷P1886

第一思路暴力,两个 for  循环就搞定了,但这样的算法时间复杂度为 O(n^2),肯定会超时。所以要优化,这就用上了单调队列。

以求最大值为例(最小值同理),我们可以这样维护队列的值:

  • 维护队首:如果队首元素下标在当前下标的 k 个之前,弹出队首。
  • 维护队尾:比较当前元素与队尾元素的大小,若当前元素更优,弹出队尾元素,直到可以满足队列单调性后加入当前元素。因为如果对于两个元素  a_x,a_y , x<y  且 a_x<a_y,那么窗口在右端滑到 y 之后,a_x 再也不可能成为最大值。 

对于这道题,我们模拟窗口右移的过程,每右移一个单位,就将若干个元素踢出 队首或队尾 ,并将新的元素加入 队尾

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,f[1000100];
int w[1000100],v[1000100];
void get_max()//维护最大值
{
		printf("\n");
		memset(w,0,sizeof(w));
		memset(v,0,sizeof(v));
		int head=1,tail=0;
		for(int i=1;i<=n;i++){
			while(head<=tail&&w[tail]<f[i]) tail--;
			w[++tail]=f[i];//储存值
			v[tail]=i;//储存位置
			while(v[head]<=i-k&&head<tail) head++;
			if(i>=k) printf("%d ",w[head]);
		}
}
void get_min()//维护最小值
{
		int head=1,tail=0;
		for(int i=1;i<=n;i++){
			while(head<=tail&&w[tail]>f[i]) tail--;
			w[++tail]=f[i];
			v[tail]=i;
			while(v[head]<=i-k&&head<tail) head++;
			if(i>=k) printf("%d ",w[head]);
		}
}
int main()
{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		scanf("%d",&f[i]);
		get_min();
		get_max();
		return 0;//撒花
}

是不是很简单 ?

 那么进入下一个话题:

单调队列优化DP

在讲之前,先普及一下知识:

1D动态规划

指的是状态数为 O(n),每一个状态决策量为 O(n) 的动态规划方程,这样的方程直接暴力求解的时间复杂度为 O(n^2) 。(基本会 TLE

这里只讲单调队列优化1D动态规划:

在1D动态规划中,有一种 DP,转移方程一般为:

dp[i]=min(dp[i],dp[j]+f[i][j])

其中 (l[i]<=j<=r[i]) , l[i]r[i] 的序列单调不减。 min 也可以写成 max,方法是一样的。

这种 DP 可以用单调队列分 4 步进行优化:

  • 将所有小于 l[i]j 全部踢队。
  • 用队首 j 为 dp[i] 赋值,队首 head 要变化。
  • 将新元素 j 加入队尾 (j<=l[i]),队尾 tail 也要变化。
  • 维护单调队列。

基本内容就是这些,其实动脑推出 DP 方程式就行了。说得简单


版权声明:本文为Da_un原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。