上次百度之星第二场复赛出了一道单调DP,当时什么都不会,只知道有个四边形不等式什么的东西,于是套了套模板..还和大牛们对拍了,结果只拿到了60分,如果拿到100分的话,复赛也能晋级了,好在坦克已经晋级了,遗憾不大..但是这类题目最近很风靡,并且十分重要,所以赛后马上补习,四边形的证明有点繁琐,而多数题目可以转化成斜率优化,但是斜率优化的多数题目却无法转化成四边形不等式,于是重点学习了单调队列+斜率优化的DP

先介绍下单调队列……好吧,就字面上的意思..具体可以百度一下

斜率优化的话看这个论文比较爽(这篇论文不是专门讲斜率优化的,但是我学斜率优化就是从例二那里受到启发的)

然后这篇就是进阶了,里边的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)),非常的灵活.

Popularity: 45% [?]