《动态规划优化》PPT课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,浅谈动态规划优化,2009,曹文信息学奥林匹克夏令营,Author:Will,简介,动态规划优化的主要方法：,1,、降维（优化状态）,2,、优化转移,3,、常数优化,1.,降维,降维是一个通用的说法，其实质就是通过改变动态规划的状态含义，或者抛弃一些冗余状态环节，达到减少状态，加速动态规划的目的,1.1,转变思路,很多时候，当得出某种动态规划模型的时候，不要着急动手，而是需要仔细思考一下，是不是有更好的状态表示方法,多积累经验，同时又不能拘泥于死板的模型理论，要有创新意识。,例题,给定,N*M,的空白棋盘，在其中放任意放车（可以不放），要使得放在棋盘上的车两两不能攻击，求方案总数,MOD P,的值。,思路一,按照基本的状态压缩动态规划模型进行解答。,optKS,表示已经放了前,K,行，并且每一列是否有车的状态为,S,（,S,为一个,0/1,的,2,进制序列，那一位为,1,则表示对应一列已经放过了一个车）的合法方案的数量。,比如,opt2(101),2,即表示前,2,行放了车且第,1,，,3,列有车的状态。,思路一,则转移就是枚举这一行放还是不放，如果放的话则枚举所有没有放车的行，将对应的,2,进制位标记为,1,，进行转移。,时间复杂度,O(NM2,M,),空间复杂度,O(2,M,),但是,如果,N,M1000,该怎么办呢？,思路二,换一个角度来分析问题,可以发现，我们需要知道的只是有多少列目前没有放车，并不需要知道具体是哪些列没有放车！,因此,optk(101),2,和,optk(110),2,是本质等价的。,于是我们可以把状态改为：,optkS,表示放置了前,k,行，并且有,S,列没有放置。,思路二,此时转移稍有不同,optk+1S=optkS+optkS+1*(S+1),此时时间复杂度为,O(NM),空间复杂度为,O(NM),问题得到了解决,可见对问题透彻的分析是得出最有效规划方式的前提。,1.2,抛弃冗余,很多时候一些状态是不需要的，或者某些维是可以合并的。,经过合理的分析我们可以抛弃一些冗余信息，减少状态，加速转移。,例题,poet(NOI2009 day1 p2),有,N,个诗句，要每个诗句有一个长度,Li,，要将其排版，一行可以放若干诗句并且每句诗中间用一个空格隔开，有一标准长,Len,，每一行的难看度是当前行长度,C,与,Len,之差绝对值的,P,次方。,求一种最好看的排版方式使得总难看度最小。,N10000 L200 1P10,思路一,由于标准行长,L,很小我们不难想到一个如下的动态规划方法：,optKS,表示排版了前,K,个句子，并且当前行长是,S,。,对于每个状态转移就是枚举是将这个诗句放在行末还是换行。,有一个问题是：,如果一个诗句过长怎么办？那我们也将数组下标开的很大么？,思路二,仔细分析，不难发现，第二维状态是没有用的。,我们需要知道只是每一行最后一个诗句是那个就可以了，并不用关心每行具体多长。,我们抛弃第二维：,optK,表示安排了前,K,个诗句并且第,K,个诗句在行末所能获得的最小难看度。,思路二,那么转移就是,optK=min(opti+cost(i+1,K)|iK),cost(i+1,K),表示第,i+1,到第,K,个诗句放一行的难看度。,那如何利用,LL,且,Sum(j,K)L,则所有,i,之前的决策都是无用的。,思路二,时间复杂度,O(NL),空间复杂度,O(N),不难发现我们是利用,L200,这个条件在动态规划中进行了一个剪枝从而将一个空间复杂度无法估计的动态规划成功降低到了,O(N),，并成功将复杂度降低。,剔除动态规划中的冗余信息是优化动态规划的重要方面。,2.,优化转移,1,、优化转移方式,2,、预处理,3,、费用提前计算,4,、参数分离,5,、单调性,2.1,优化转移方式,基本的转移方式共有两种,1,、通过状态选择决策,2,、通过决策来更新状态,状态选择决策,对于每个状态会有一些决策来选择，我们从中选择一个最优的决策，来实现规划的过程，并完成了当前这一状态的计算。,可以认为这是一个正向过程。,一个简单的例子,optk=min(opti+1|AiAk),这是一个不下降子序列的动态规划方程,不难得到这个方法,O(NlogN),转移方式,决策更新状态,当一个状态计算完毕，那么这个状态就自然的成为了后面状态选择的一个决策，于是我们可以在刚产生这个决策的时候更新所有可能用到这个决策的状态。,可以说这是一个逆向行为的过程。,大多数时候正向方式和逆向方式是差不多的，或者正向方式优于逆向方式，当然也有例外，因此需要我们自己根据实际情况灵活选择。,例题,给,N*M,的存在一些障碍的棋盘，在其中放置,1*2,的多米诺骨牌，问合法的放置总数,MOD P,是多少。,说在前面,我们这里先介绍一种对于状态压缩动态规划转移和状态表示的一般方法按格（点）转移。,optxyS表示当前决策格为(x,y)同时2进制状态S表示当前扫描线上每个格子是否被覆盖的状况。,说在前面,x,y,OPT,x,y,(000000),2,OPT,x,y+1,(0,11,000),2,分析,不难发现我们之前选择了一种逆向转移的方式,即从当前状态枚举下一步行为，并向后,更新,这样的好处在于,（,1,）方便情况的讨论，简化转移,（,2,）避免了很多不可能出现的状态,（,3,）加速了决策,时间复杂度,O(N2,M,),其实，还有一些情况是只有这种更新方式才能优化的，限于篇幅和难度问题这里就不多说了,2.2,预处理,预处理就是将动态规划中常用的一些计算环节预先处理好，方便动态规划中重复用到，很多时候利用这种并行计算的问题是可以大大降低算法复杂度的。,例题,Grid(BOI2008),有分成,N*M,格的土地，每个土地有一个工作时间，现在可以将这些土地分成,(r+1)*(s+1),块，每块由一个工作人员来完成工作，问最快能多长时间完成全部格子上的工作？,rN18 sM18,分析,简单的想法是首先枚举横向如何对土地进行分割，然后再对纵向进行动态规划。,枚举部分我们不多说，这里共需要,C(N,r),的时间，我们用数组,lis,记录分割情况,关于动态规划，不难得到如下方程：,optik,表示第,i,个竖线为第,k,个分割线。,转移比较简单,optik=minmax(optjk-1,f(j,i),分析,代价,f,我们可以边转移边计算。,我们从,i,开始从后往前枚举,j,，那么我们显然每次只需要,O(N),的代价就可以计算出当前的,f,。,动态规划的时间复杂度为,O(rsM,2,),算法的总体复杂度为,O(C(N,r)rsM,2,),TLE,！,优化,1.,预处理出,sumxy,数组，记录矩形,(1,1)-(x,y),中每个格子的工作量之和。,则对于任意矩形，我们都可以在,O(1),时间内计算出部分和。,2.,搜索完行的拆分之后，我们预处理出所有,f,数组。,计算,f,数组的时间复杂度为,O(M,2,r),此时动态规划复杂度为,O(M,2,s),总复杂度降为,O(C(N,r)M,2,(r+s),2.3,费用提前计算,在动态规划问题中很多时候计算转移代价成了我们一个很棘手的问题，有些时候我们可能要花费很多的力气来计算某一些特定状态下的费用（比如边界状态等等）,其实很多时候我们可以用一些方法，把费用计算花去的时间平摊到其他的地方，从而优化动态规划,例题,Sue,的小球,(,sdtsc 2008),天空中有,N,个坐标为,(xi,yi),的小球，并会以,vi,速度匀速下降，这个小球的价值就是其,y,坐标的,1000,分之一,你有一个在,x,坐标轴上滑行的飞行器，可以以单位速度在,x,轴上平移，只要和小球到同一,x,坐标就能收获那个小球。,假设你一开始在,(0,0),，并且希望收获所有小球，问可能的最大收益是？,N1000,分析,由于所有小球的,x,坐标是不变的，因此我们按照,x,坐标将小球排序。,观察一个性质：,我们获得球必然是一个连续区间。,因此不难得出动态规划表示方法：,optLR0/1,表示获得球的区间是,L,R,，同时此时飞行器在左边,/,右边球所对应的,x,坐标。,分析,但是，如何计算代价呢？,考虑到一个很好的性质：飞行器的移动速度是单位速度。,一种简单的方式是增加一维时间：,optLRT0/1,表示时刻,T,此时的状态。,可以使用队列保存可行状态，再使用更新状态的方法进行转移。,N=1000,！,TLE+MLE!,优化,现在问题的关键在于如何快速的计算费用。,我们现在纠结的问题在于，我们并不知道之前我们是如何行走的，所以如果没有,T,，我们并不知道当前我们面对的球到底是多少价值。,优化,我们不妨换个思路，为什么要去纠结于之前的状态呢？,当我们做了一个决策之后，对后面的影响我们是知道的，为什么不能把握这一我们清楚的信息呢？,道理很清楚：,不要纠结于过去，把眼光方向未来！,天涯何处无芳草，未来永远是光明的！,优化,每次决策后，我们将这一次移动对所有我们还没有得到的小球产生的费用损失都在决策时计算。,我们可以看作小球都没有动，只是在我们每次决策是损失了一些价值。,假设当前移动花费了时间,T,，我们还没有得到的小球的速度和是,SV,，那么损失的代价就是,T*SV/1000,问题的解决,我们用,SI,记录前,I,个小球的速度和,那么我们的转移方程就是：,optLR0/1,-(SN-SR+SL-1)*T/1000,+value,optLR0/1,时空复杂度,O(N,2,),2.4,参数分离,这是一个信息学竞赛中非常重要的手段，当然难度也比较大，这里限于篇幅和难度，只是简单说一下。,参数分离就是通过数学变形将和决策有关的变量和状态有关的变量分开，从而发现一些性质来优化动态规划。,例题,Triangles(POI07-08 StageIII),给定平面上N1000个点，则显然会构成N(N-1)(N-2)/3个三角形,求所有这些三角形的面积和,预备知识,首先必须要知道叉积,向量,a=(x1,y1),，,b=(x2,y2),则有：,a b=x1*y2 x2*y1,=|a|b|sin,为有向角度,因此只要保证方向为正，那么向量,a,和,b,组成的三角形面积即为,(a b)/2,分析,首先我们花,O(N),的时间枚举左下角,c,所有需要计算的点都以点,c,为原点建系,假设坐标为,xi,和,yi,按极角排序后，我们要求的就是,不难得出一个,O(N,3,),的算法,优化,我们给式子做一个变形,我们用,Syi,记录,yi,到,yN,的和，,Sxi,记录,xi,到,xN,的和，那么要求的就是,AC,注意此时,i,和,j,这两个参数相互分离！,2.5,单调性,这是很难的一部分内容，个人认为，如果是把目标放在,NOIP,级别的比赛，是不用掌握这部分内容的。,但是，本着更高更快更强的精神：,为了未来我们那崇高的理想！,我们不应该着眼于现在！,不要为现在而伤感，要相信自己！,为了传递这份精神，还是浅浅谈一下,2.5.1,四边形不等式,权函数,w(i,j),，对于,ii j j,如果满足,w(i,j)w(i,j),则称,w,满足区间单调性,如果满足,w(i,j)+w(i,j,),w(,i,j)+w(i,j,),则称,w,满足四边形不等式,记忆