动态规划优化.ppt

动态规划优化
第1页，本讲稿共48页
简介
动态规划优化的主要方法：
1、降维（优化状态）
2、优化转移
3、常数优化
第2页，本讲稿共48页

降维是一个通用的说法，其实质就是通过改变动态规划的状态含义，或认为这是一个正向过程。
一个简单的例子
opt[k]=min(opt[i]+1|A[i]<A[k])
这是一个不下降子序列的动态规划方程
不难得到这个方法O(NlogN)转移方式
第18页，本讲稿共48页

当一个状态计算完毕，那么这个状态就自然的成为了后面状态选择的一个决策，于是我们可以在刚产生这个决策的时候更新所有可能用到这个决策的状态。
可以说这是一个逆向行为的过程。
大多数时候正向方式和逆向方式是差不多的，或者正向方式优于逆向方式，当然也有例外，因此需要我们自己根据实际情况灵活选择。
第19页，本讲稿共48页

给N*M的存在一些障碍的棋盘，在其中放置1*2的多米诺骨牌，问合法的放置总数MOD P是多少。
第20页，本讲稿共48页

我们这里先介绍一种对于状态压缩动态规划转移和状态表示的一般方法——按格（点）转移。
opt[x][y][S]表示当前决策格为(x,y)同时2进制状态S表示当前扫描线上每个格子是否被覆盖的状况。
第21页，本讲稿共48页

OPT
[x]
[y]
[(000000)2]
OPT
[x]
[y+1]
[(011000)2]
第22页，本讲稿共48页

不难发现我们之前选择了一种逆向转移的方式——即从当前状态枚举下一步行为，并向后更新
这样的好处在于
（1）方便情况的讨论，简化转移
（2）避免了很多不可能出现的状态
（3）加速了决策
时间复杂度 O(N2M)
其实，还有一些情况是只有这种更新方式才能优化的，限于篇幅和难度问题这里就不多说了
第23页，本讲稿共48页
预处理
预处理就是将动态规划中常用的一些计算环节预先处理好，方便动态规划中重复用到，很多时候利用这种并行计算的问题是可以大大降低算法复杂度的。
第24页，本讲稿共48页

Grid(BOI2008)
有分成N*M格的土地，每个土地有一个工作时间，现在可以将这些土地分成(r+1)*(s+1)块，每块由一个工作人员来完成工作，问最快能多长时间完成全部格子上的工作？
r<N<18 s<M<18
第25页，本讲稿共48页

简单的想法是首先枚举横向如何对土地进行分割，然后再对纵向进行动态规划。
枚举部分我们不多说，这里共需要C(N,r)的时间，我们用数组lis记录分割情况
关于动态规划，不难得到如下方程：
opt[i][k]表示第i个竖线为第k个分割线。
转移比较简单
opt[i][k]=min{max(opt[j][k-1],f(j,i))}
第26页，本讲稿共48页

代价f我们可以边转移边计算。
我们从i开始从后往前枚举j，那么我们显然每次只需要O(N)的代价就可以计算出当前的f。
动态规划的时间复杂度为O(rsM2)
算法的总体复杂度为O(C(N,r)rsM2)
第27页，本讲稿共48页

[x][y]数组，记录矩形(1,1)-(x,y)中每个格子的工作量之和。
则对于任意矩形，我们都可以在O(1)时间内计算出部分和。
，我们预处理出所有f数组。
计算f数组的时间复杂度为O(M2r)
此时动态规划复杂度为O(M2s)
总复杂度降为O(C(N,r)M2(r+s))
第28页，本讲稿共48页
费用提前计算
在动态规划问题中很多时候计算转移代价成了我们一个很棘手的问题，有些时候我们可能要花费很多的力气来计算某一些特定状态下的费用（比如边界状态等等）
其实很多时候我们可以用一些方法，把费用计算花去的时间平摊到其他的地方，从而优化动态规划
第29页，本讲稿共48页

Sue的小球(sdtsc 2008)
天空中有N个坐标为(xi,yi)的小球，并会以vi速度匀速下降，这个小球的价值就是其y坐标的1000分之一
你有一个在x坐标轴上滑行的飞行器，可以以单位速度在x轴上平移，只要和小球到同一x坐标就能收获那个小球。
假设你一开始在(0,0)，并且希望收获所有小球，问可能的最大收益是？
N<1000
第30页，本讲稿共48页

由于所有小球的x坐标