首页 > 其他分享 >单调队列优化DP

单调队列优化DP

时间:2023-01-11 21:12:38浏览次数:70  
标签:le min 队列 sum DP 单调

今天学习了单调队列优化DP,其模型为:

\[f_i=\min/\max_{L(i)\le j\le R(i)}\lbrace kf_j+val(i,j)\rbrace \]

其中\(L,R\)是具有单调性的函数,\(val(i,j)=h_1(i)+h_2(j)\),是分别关于\(i,j\)的函数之和。

其原理在于:

对于\(f_i\)的两个在范围内的决策\(j,k\)而言,由于\(L,R\)具备单调性,故设决策\(j\)在时间次序上优于\(k\),若在此基础上,(以\(\min\)函数为例),\(h_2(j)<h_2(k)\),此时的\(j\)在当前和以后都会优于\(k\),进而排出掉决策\(k\)。

其常见应用在于:

  1. 维护区间最值等信息
  2. 对最优化DP进行优化

在这里,举出几个单调队列的应用:

维护定长区间最大值

问题描述:在\(O(n)\)的时间复杂度内求出每个位置\(i\)中\(\min_{i-m\le k<i}a_k\)

分析:在单调队列的过程中,每次取队头(如果队头距离过远就先出队)为最优解,然后插入的时候一直将比其大的数删掉即可。

核心Code:

for(int i=1;i<=n;i++)read(a[i]);
	int h=1,t=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&i-q[h]>m)h++;
		if(h<=t)printf("%d\n",a[q[h]]);
		else puts("0");
		while(h<=t&&a[q[t]]>=a[i])t--;
		q[++t]=i;
	} 

维护限长最大子段和

题目描述:给定数列\(a_1\sim a_n\),求出其长度不超过\(m\)的最大子段和。

考虑DP,设\(f_i\)表示以\(a_i\)为结尾的答案,则容易得到:

\(f_i=\min_{i-m<k\le i}sum_i-sum_{k-1}\)

将\(sum_i\)提出,实际需要维护的是\(\max sum_{k-1}\),扔进单调队列即可。

	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)a[i]+=a[i-1];
	t=1,q[1]=0;
	for(int i=1;i<=n;i++){
		while(h<=t&&i-q[h]>m)h++;
		if(h<=t)ans=max(ans,a[i]-a[q[h]]);
		while(h<=t&&a[q[t]]>=a[i])t--;
		q[++t]=i;
	}
	cout<<ans;

维护可消除最大子段和

题目描述:给定一个长度为\(n\) 的序列,你有一次机会选中一段连续的长度不超过\(m\)的区间,将里面所有数字全部修改为 0。

请找到最长的一段连续区间,使得该区间内所有数字之和不超过\(p\) 。\(1\le a_i\)

这里注意到:对于右端点向右进行移动,左端点是具备单调性,这启发我们维护右端点,左端点看情况增加。

而由于所有的数都是正整数,所以选中区间长度一定是\(m\),于是我们可以预处理出每一个长为\(m\)的区间之和,使用单调队列维护它。

设\(f_i\)表示以\(i\)为区间右端点的答案,则\(f_i=\max len\),这个\(len\)满足\(sum_{i}-sum_{i-len}-(sum_{k+m-1}-sum_{k-1})\)。而之前说到了,左端点具有单调性,所以我们可以设出\(l\),每次判断不得不增加时再进行增加。所以我们可以使用单调队列来维护后面的\((sum_{k+m-1}-sum_{k-1})\)来更新答案。

Code:

	cin>>n>>p>>d;ans=d;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)f[i]=sum[i+d-1]-sum[i-1];
	int l=1;t=1,q[1]=0;
	for(int i=d;i<=n;i++){
		while(h<=t&&f[q[t]]<=f[i-d+1])t--;
		q[++t]=i-d+1;
		while(sum[i]-sum[l-1]-f[q[h]]>p){
			++l;while(h<=t&&q[h]<l)h++;
		}
		if(q[h]>=l)ans=max(i-l+1,ans);
	}

分段单调队列

这里就没例题了,实在想要可以用单调队列做一做龙珠。事实上只需要预处理最小值,不需要单调队列

也即,我们对答案的计算可以分为:

\(ans_i=\min\lbrace f_1(k)+g_1(i),f_2(k)+g_2(i), f_3(k)+g_3(i)… \rbrace\)

这种多种不同决策造成的可能。常见的是拆开abs,分类讨论,多种情况等等。在这样的问题下,我们可以对每一个部分都开一个单调队列进行维护,最后计算答案即可。

模型总结

总的来说,一般使用单调队列优化DP的动态规划方程都是如下形式($\max $同样):

\[f_i=\min_{L(i)\le k\le R(i)}\lbrace g_1(j)+g_2(i)\rbrace \]

其中\(L,R\)俩个函数具备相同的非严格单调性。在此时,我们可以使用单调队列维护\(g_1(j)\),一般而言步骤如下:

  1. 检查队头,剔除越界的决策
  2. 使用队头更新答案
  3. 将新的决策插入队列尾,在插入同时排除掉不会比新决策优秀的决策

注意事项

  1. 注意到>=,>,<=,<的区别,尤其小心边界
  2. 检查是否需要提前在队列中插入初始值(一般是0)
  3. 分类讨论很重要
  4. 所有的操作都是在队列里有元素的情况下进行的
  5. 有时需要先将决策插入,再更新答案,具体情况具体分析
  6. ~~实在单调队列调不好了推荐换优先队列无脑插,一般可以拿到70%90%的分~
  7. 推荐手写队列,STL用不好会蹦出奇奇怪怪的错误,而且常数大

标签:le,min,队列,sum,DP,单调
From: https://www.cnblogs.com/oierpyt/p/17044901.html

相关文章

  • C++实现顺序队列(循环队列)相关操作代码
    #include<iostream>#include<cstdlib>usingnamespacestd;#defineMAXSIZE100#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;typedefintElemtype......
  • 关于华普物联HP-ERS-T200串口服务器UDP 连接互联网服务器操作案例
    本案例使用“路由侠”模拟互联网服务器,使用“路由侠”生成的外网地址进行测试。   硬件连接 将HP-ERS-T200通过USB转RS232串口线连接到PC的USB口上,HP......
  • 关于华普物联HP-ERS-T200串口服务器UDP局域网通讯案例
    硬件连接两个HP-ERS-T200分别通过USB转RS232串口线连接到PC的USB口上,通过上位机设置参数,设置完参数后,将两个HP-ERS-T200通过网线直连。 电脑COM口号确认......
  • 剑指 Offer 09. 用两个栈实现队列
    剑指Offer09.用两个栈实现队列用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数......
  • 理解wordpress中的taxonomy category与term
    最近接触了很多PHP的东西,也学到了很多新的,就想着也利用热乎的知识优化一下基于​​Wordpress​​的极风游官网。实际操作过程中,发现其实除了php的知识以外,wordpress也还是......
  • 【做题笔记】动态规划专题(DP)
    这里记录笔者这几天做的有关于dp的题目。树形dp#1P1122最大子树和题目链接:https://www.luogu.com.cn/problem/P1122题意:选出一个联通分量,使得联通分量的点的点权......
  • 基于单调性的 dp 优化
    决策单调性决策单调性一般用于最优性问题当中,即一个状态只能从一个最优的状态转移,该最优状态称之为最优点。决策单调性就是指最优点随dp转移单调移动。一般如果能够将......
  • 大话数据结构--栈与队列
    栈与队列总目录前言四、栈与队列4.1初始栈与队列4.2栈的定义4.2.1栈的定义1.一些要注意的点4.2.2进栈出栈变化形式4.3栈的抽象数据类型4.4栈的顺序存储结构及实现4.4.1......
  • 数据结构 玩转数据结构 8-6 基于堆的优先队列
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13743 1重点关注1.1基于堆的优先队列见3.1 1.2泛型使用见3.1方法中......
  • 消息队列常见的使用场景
    本文已经收录到Github仓库,该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招......