http://www.notonlysuccess.com/?p=740
先介绍下单调队列……好吧,就字面上的意思..具体可以百度一下
斜率优化的话看这个论文比较爽(这篇论文不是专门讲斜率优化的,但是我学斜率优化就是从例二那里受到启发的)
然后这篇就是进阶了,里边的5个例题从浅到深解析的很好
从易到难找了几道题目(后边标记的复杂度都是算决策那维的复杂度)
单纯的单调队列:
志愿者选拔 O(n)
最最入门的单调队列,而且是很形象的排队问题
Sliding Window O(n)
同上题
Max Sum of Max-K-sub-sequence O(n)
差不多同上题,不过就是先求[1,i]的和,然后循环的,延迟一倍处理一下
单调队列优化的DP:
Trade O(n)
本来是O(MaxP *MaxP *T*T)的,T的那一维比较好优化,要取W前天最好的,那么每次都记录前W天最好的,而MaxP那一维的话我是买入做一次单调队列,卖出再做一次.最后复杂度O(Maxp*T)
SubsequenceO(n)
记录单调递增和递减两个队列,然后判断队列第一个元素是否在范围内,不在的话更新最前面一个点
【noi2005试题】瑰丽华尔兹 O(n)
这题比较好玩,状态是[K][N][M],每次偏移的时候取前T个点里最优的那个值(设偏移T = e-s+1秒钟),转移方程其实就是
以向下偏移为例: dp[k][i][j] = max{dp[k-1][i-l][j] + (i-l)}(0<=l<=T) ,于是我们可以用单调队列优化掉枚举l的那一维
Cut the SequenceO(n*logn)
这次每段的决策长度不是确定的,但是可以看出下界是单调递增的,我们先二分把每个点的决策下界求出来
每次的最佳决策点其实是dp[ limit[i] ] + que[lo].val(limit[i]是i的决策下界)所以为了保证这个下界最好,要建一个BST来维护最小值(这篇论文里有详细介绍)
Sequence Partitioning(同上题,需要用BST优化) O(n*logn*logn)
cdq的神题,仔细观察研究后可以发现二分答案之后和上题一样.
斜率优化:
MAX Average Problem O(n)
这是基础,裸的数形结合:第一篇树形结合题目里的例题
下边的题都是需要构造(x,y)和斜率的:
锯木场选址 O(n)
经典题目,第二篇论文里有类似的(例四.仓库建设 Storage)
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1010 O(n)
第二篇论文里的例三.玩具装箱Toy(不过论文里写的烦了O(nlogn),用转化成x,y,斜率的方法可以O(n)解决)
Lawrence O(n)
这题也可用四边形不等式解决,证明出来就好.斜率也可以OK
Print ArticleO(n)
比较简单的斜率.
BST 解决不单调的DP问题=.=(为了这题,我特地去学了sbt和splay)
【noi2007试题】货币兑换 O(n*logn)
点的坐标(x,y)不递增,斜率也不递增.于是悲剧了,单调队列没办法从中间插入维护,所以这类题目就要用到BST这类数据结构来求最大值,还有从中间斜率和点的单调性.论文上的最后一道例题
总结
做了这么多题之后发现其实单调队列+斜率的DP只要推出X,Y,还有斜率之后,差不多就是模板题了.
对于一些dp[...][i] = max(dp[...][j]+w[j,i])的问题,只要能把w[j,i]化简成类似( cost[j] – cost[i-1] – sum[i-1] * (sum[j] – sum[i-1]) 这个是Lawrence这题的化简)只和j,i自身相关的表达式,就能用上述的方法优化(符合单调性的话就O(n),不符合就可以用splay优化到O(nlogn)),非常的灵活.
分享到:
相关推荐
DP的单调队列优化-Yuiffy.pdf
【专辑】单调队列+斜率优化的DP 01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 ...
多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包单调队列优化问题多重背包...
多重背包单调队列优化问题.pdf
第5章 单调队列优化动态规划(2021.08.19).pdf
动态规划优化, 斜率优化 凸包优化 决策单调性 二分优化
第5章 单调队列优化动态规划(2021.08.23).pdf
单调栈&&单调队列
本人自己做的类,虽说只是测试版,但已经可以胜任一部分任务了 PS:双向队列是基础类,单调队列、单调栈是结果类
单调队列(PASCAL)-2020.06.09.pdf
与一维单调队列类似,二维单调队列也是维护一个递增(或递减)的队列,但是队列中的元素是二维的。 二维单调队列通常用于解决滑动窗口等问题,它可以在滑动窗口的基础上维护一些额外的信息,以便在常数时间内处理...
本文收录了在时间效率上动态规划的三大优化:四边形不等式,斜率优化,单调队列优化。另外,也收录了解决NP问题小规模求解中,优于搜索的状态压缩动态规划。 关键词:动态规划优化,四边形不等式,斜率优化,单调...
单调队列,斜率dp,集训队论文
http://ybt.ssoier.cn:8088 信息学奥赛一本通(提高篇)测试数据\第5部分 动态规划(提高篇) 第5章 单调队列优化动态规划 测试数据
单调栈和单调队列.pdf
单调队列.md
单调队列 采用汇编语言实现单调队列,用于计算机组成原理课程设计
2021年考研高数函数单调性+奇偶性求法总结.pdf
浅谈几类背包题-浅谈几类背包题-单调队列优化(PASCAL).pdf
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138