动态规划2.ppt

动态规划优化初步
常州市第一中学吴争锴
说明
本篇主要从实用角度讲解一些优化技巧,证明神马的从略。
四边形不等式
应用范围:
形如f[i][j]=max(f[i][k]+f[k][j]+w(i,j))类DP方程
若对任意的a <= b <= c <= d,有w(a,d) + w(b,c) >= w(a,c) + w(b,d),则称此不等式为四边形不等式。
对于区间类DP,如果权函数满足四边形不等式,那么其决策满足单调性。
四边形不等式
例子:合并石子
容易证明权函数满足四边形不等式,而且是相等的特殊情况
则如果记f[i][j]取到最优值的k为c[i][j],那么我们有c[i][j-1]<=c[i][j]<=c[i+1][j]。
这样能够将合并石子的复杂度降为O(n^2)
请一个同学来证明
单调队列
单调队列本身作为一个数据结构就是一个队列。只不过我们用这个队列来维护单调性而已。
下面来看单调队列中模型最裸的一题。掌握了这题至少可以说是掌握了单调队列本身。
单调队列
Poj 2823 Window:n个数,有一个长度为m的窗口在从左向右移动,求出每个长度为m的区间里的最大值。(如果大家提交的话需要优化读入)
M<=N<=1000000
讨论做法:
线段树:常数过大
堆:还是带有logn
能否找寻线性算法
单调队列
我们不妨把这题写成一个动态规划:
F[i]=max(a[j]|i-m+1<=j<=i)i>=m
我们发现如果i<j且a[i]<a[j],那么对于j之后的位置a[i]已经毫无价值,因为它会比j更早逐出可行的选择区域,然后在区域中时又永远不优于a[j]
因此,我们维护这样一个单调性,每次在队尾添加元素,然后满足队列中i递增而a[i]递减。
每次还需要判断队头是否已经到可选择范围之外。
单调队列
那么这个做法的复杂度是多少呢?
初看之下复杂度似乎不好估计
每个元素最多入队一次,出队一次
因此复杂度为O(n)
通过这例子,大家应该对单调队列本身熟悉了。
那么,这题当中的转移方程是静态的,实际上,如果决策满足单调性都可以用单调队列维护。
凸完全单调性
对于一个权函数w(i,j),如果它满足w(x,i+1) - w(x,i)随x单调不增,也就是w(x,i+1) - w(x,i) >= w(x+1,i+1) - w(x+1,i),则称这个权函数满足凸完全单调性。
由凸完全单调性可以推出四边形不等式,反之也可,因此这两者完全等价。
那么决策单调性是什么呢?
决策单调性
这里采用比较简洁易懂的方法:对于某一个x,如果有f[i] + w(i,x) >= f[j] + w(j,x),其中i < j,那么对于任何的y > x,f[i] + w(i,y) >= f[j] + w(j,y)成立。也就是说,一旦某一个时刻,决策i没有决策j好,那么以后决策i也不会有决策j好。
那么这有什么用呢?
这里我们看一下小戴的ppt