动态规划优化

动态规划优化第1页，共48页，2023年，2月20日，星期日简介动态规划优化的主要方法：1、降维（优化状态）2、优化转移3、常数优化第2页，共48页，2023年，2月20日，星期日1.降维降维是一个通用的说法，其实质就是通过改变动态规划的状态含义，或者抛弃一些冗余状态环节，达到减少状态，加速动态规划的目的第3页，共48页，2023年，2月20日，星期日1.1转变思路很多时候，当得出某种动态规划模型的时候，不要着急动手，而是需要仔细思考一下，是不是有更好的状态表示方法多积累经验，同时又不能拘泥于死板的模型理论，要有创新意识。第4页，共48页，2023年，2月20日，星期日1.1.1例题给定N*M的空白棋盘，在其中放任意放车（可以不放），要使得放在棋盘上的车两两不能攻击，求方案总数MODP的值。第5页，共48页，2023年，2月20日，星期日1.1.1.1思路一按照基本的状态压缩动态规划模型进行解答。opt[K][S]表示已经放了前K行，并且每一列是否有车的状态为S（S为一个0/1的2进制序列，那一位为1则表示对应一列已经放过了一个车）的合法方案的数量。比如opt[2][(101)2]即表示前2行放了车且第1，3列有车的状态。第6页，共48页，2023年，2月20日，星期日1.1.1.1思路一则转移就是枚举这一行放还是不放，如果放的话则枚举所有没有放车的行，将对应的2进制位标记为1，进行转移。时间复杂度O(NM2M)空间复杂度O(2M)但是……如果N,M>1000该怎么办呢？第7页，共48页，2023年，2月20日，星期日1.1.1.2思路二换一个角度来分析问题可以发现，我们需要知道的只是有多少列目前没有放车，并不需要知道具体是哪些列没有放车！因此opt[k][(101)2]和opt[k][(110)2]是本质等价的。于是我们可以把状态改为：opt[k][S]表示放置了前k行，并且有S列没有放置。第8页，共48页，2023年，2月20日，星期日1.1.1.2思路二此时转移稍有不同opt[k+1][S]=opt[k][S]+opt[k][S+1]*(S+1)此时时间复杂度为O(NM)空间复杂度为O(NM)问题得到了解决可见对问题透彻的分析是得出最有效规划方式的前提。第9页，共48页，2023年，2月20日，星期日1.2抛弃冗余很多时候一些状态是不需要的，或者某些维是可以合并的。经过合理的分析我们可以抛弃一些冗余信息，减少状态，加速转移。第10页，共48页，2023年，2月20日，星期日1.2.1例题poet(NOI2009day1p2)有N个诗句，要每个诗句有一个长度Li，要将其排版，一行可以放若干诗句并且每句诗中间用一个空格隔开，有一标准长Len，每一行的难看度是当前行长度C与Len之差绝对值的P次方。求一种最好看的排版方式使得总难看度最小。N<10000L<2001<P<10第11页，共48页，2023年，2月20日，星期日1.2.1.1思路一由于标准行长L很小我们不难想到一个如下的动态规划方法：opt[K][S]表示排版了前K个句子，并且当前行长是S。对于每个状态转移就是枚举是将这个诗句放在行末还是换行。有一个问题是：如果一个诗句过长怎么办？？？那我们也将数组下标开的很大么？？第12页，共48页，2023年，2月20日，星期日1.2.1.2思路二仔细分析，不难发现，第二维状态是没有用的。我们需要知道只是每一行最后一个诗句是那个就可以了，并不用关心每行具体多长。我们抛弃第二维：opt[K]表示安排了前K个诗句并且第K个诗句在行末所能获得的最小难看度。第13页，共48页，2023年，2月20日，星期日1.2.1.2思路二那么转移就是opt[K]=min(opt[i]+cost(i+1,K)|i<K)cost(i+1,K)表示第i+1到第K个诗句放一行的难看度。那如何利用L<200的条件呢？用Sum(L,R)表示第L到第R个诗句放一行的总长如果对于i，存在j使得Sum(i,j-1)>L且Sum(j,K)>L则所有i之前的决策都是无用的。第14页，共48页，2023年，2月20日，星期日1.2.1.2思路二时间复杂度O(NL)空间复杂度O(N)不难发现我们是利用L<200这个条件在动态规划中进行了一个剪枝从而将一个空间复杂度无法估计的动态规划成功降低到了O(N)，并成功将复杂度降低。剔除动态规划中的冗余信息是优化动态规划的重要方面。第15页，共48页，2023年，2月20日，星期日2.优化转移1、优化转移方式2、预处理3、费用提前计算4、参数分离5、单调性第16页，共48页，2023年，2月20日，星期日2.1优化转移方式基本的转移方式共有两种1、通过状态选择决策2、通过决策来更新状态第17页，共48页，2023年，2月20日，星期日2.1.1状态选择决策对于每个状态会有一些决策来选择，我们从中选择一个最优的决策，来实现规划的过程，并完成了当前这一状态的计算。可以认为这是一个正向过程。一个简单的例子opt[k]=min(opt[i]+1|A[i]<A[k])这是一个不下降子序列的动态规划方程不难得到这个方法O(NlogN)转移方式第18页，共48页，2023年，2月20日，星期日2.1.2决策更新状态当一个状态计算完毕，那么这个状态就自然的成为了后面状态选择的一个决策，于是我们可以在刚产生这个决策的时候更新所有可能用到这个决策的状态。可以说这是一个逆向行为的过程。大多数时候正向方式和逆向方式是差不多的，或者正向方式优于逆向方式，当然也有例外，因此需要我们自己根据实际情况灵活选择。第19页，共48页，2023年，2月20日，星期日2.1.2.1例题给N*M的存在一些障碍的棋盘，在其中放置1*2的多米诺骨牌，问合法的放置总数MODP是多少。第20页，共48页，2023年，2月20日，星期日2.1.2.1.1说在前面我们这里先介绍一种对于状态压缩动态规划转移和状态表示的一般方法——按格（点）转移。opt[x][y][S]表示当前决策格为(x,y)同时2进制状态S表示当前扫描线上每个格子是否被覆盖的状况。第21页，共48页，2023年，2月20日，星期日2.1.2.1.1说在前面OPT[x][y][(000000)2]OPT[x][y+1][(011000)2]第22页，共48页，2023年，2月20日，星期日2.1.2.1.2分析不难发现我们之前选择了一种逆向转移的方式——即从当前状态枚举下一步行为，并向后更新这样的好处在于（1）方便情况的讨论，简化转移（2）避免了很多不可能出现的状态（3）加速了决策时间复杂度O(N2M)其实，还有一些情况是只有这种更新方式才能优化的，限于篇幅和难度问题这里就不多说了第23页，共48页，2023年，2月20日，星期日2.2预处理预处理就是将动态规划中常用的一些计算环节预先处理好，方便动态规划中重复用到，很多时候利用这种并行计算的问题是可以大大降低算法复杂度的。第24页，共48页，2023年，2月20日，星期日2.2.1例题Grid(BOI2008)有分成N*M格的土地，每个土地有一个工作时间，现在可以将这些土地分成(r+1)*(s+1)块，每块由一个工作人员来完成工作，问最快能多长时间完成全部格子上的工作？r<N<18s<M<18第25页，共48页，2023年，2月20日，星期日2.2.1.1分析简单的想法是首先枚举横向如何对土地进行分割，然后再对纵向进行动态规划。枚举部分我们不多说，这里共需要C(N,r)的时间，我们用数组lis记录分割情况关于动态规划，不难得到如下方程：opt[i][k]表示第i个竖线为第k个分割线。转移比较简单opt[i][k]=min{max(opt[j][k-1],f(j,i))}第26页，共48页，2023年，2月20日，星期日2.2.1.1分析代价f我们可以边转移边计算。我们从i开始从后往前枚举j，那么我们显然每次只需要O(N)的代价就可以计算出当前的f。动态规划的时间复杂度为O(rsM2)算法的总体复杂度为O(C(N,r)rsM2)第27页，共48页，2023年，2月20日，星期日2.2.1.2优化1.预处理出sum[x][y]数组，记录矩形(1,1)-(x,y)中每个格子的工作量之和。则对于任意矩形，我们都可以在O(1)时间内计算出部分和。2.搜索完行的拆分之后，我们预处理出所有f数组。计算f数组的时间复杂度为O(M2r)此时动态规划复杂度为O(M2s)总复杂度降为O(C(N,r)M2(r+s))第28页，共48页，2023年，2月20日，星期日2.3费用提前计算在动态规划问题中很多时候计算转移代价成了我们一个很棘手的问题，有些时候我们可能要花费很多的力气来计算某一些特定状态下的费用（比如边界状态等等）其实很多时候我们可以用一些方法，把费用计算花去的时间平摊到其他的地方，从而优化动态规划第29页，共48页，2023年，2月20日，星期日2.3.1例题Sue的小球(sdtsc2008)天空中有N个坐标为(xi,yi)的小球，并会以vi速度匀速下降，这个小球的价值就是其y坐标的1000分之一你有一个在x坐标轴上滑行的飞行器，可以以单位速度在x轴上平移，只要和小球到同一x坐标就能收获那个小球。假设你一开始在(0,0)，并且希望收获所有小球，问可能的最大收益是？N<1000第30页，共48页，2023年，2月20日，星期日2.3.1.1分析由于所有小球的x坐标是不变的，因此我们按照x坐标将小球排序。观察一个性质：我们获得球必然是一个连续区间。因此不难得出动态规划表示方法：opt[L][R][0/1]表示获得球的区间是[L,R]，同时此时飞行器在左边/右边球所对应的x坐标。第31页，共48页，2023年，2月20日，星期日2.3.1.1分析但是，如何计算代价呢？考虑到一个很好的性质：飞行器的移动速度是单位速度。一种简单的方式是增加一维时间：opt[L][R][T][0/1]表示时刻T此时的状态。可以使用队列保存可行状态，再使用更新状态的方法进行转移。第32页，共48页，2023年，2月20日，星期日2.3.1.2优化现在问题的关键在于如何快速的计算费用。我们现在纠结的问题在于，我们并不知道之前我们是如何行走的，所以如果没有T，我们并不知道当前我们面对的球到底是多少价值。第33页，共48页，2023年，2月20日，星期日2.3.1.2优化我们不妨换个思路，为什么要去纠结于之前的状态呢？当我们做了一个决策之后，对后面的影响我们是知道的，为什么不能把握这一我们清楚的信息呢？道理很清楚：第34页，共48页，2023年，2月20日，星期日2.3.1.2优化每次决策后，我们将这一次移动对所有我们还没有得到的小球产生的费用损失都在决策时计算。我们可以看作小球都没有动，只是在我们每次决策是损失了一些价值。假设当前移动花费了时间T，我们还没有得到的小球的速度和是SV，那么损失的代价就是T*SV/1000第35页，共48页，2023年，2月20日，星期日2.3.1.3问题的解决我们用S[I]记录前I个小球的速度和那么我们的转移方程就是：opt[L][R][0/1]-(S[N]-S[R’]+S[L’-1])*T/1000+valueopt[L’][R’][0/1]时空复杂度O(N2)第36页，共48页，2023年，2月20日，星期日2.4参数分离这是一个信息学竞赛中非常重要的手段，当然难度也比较大，这里限于篇幅和难度，只是简单说一下。参数分离就是通过数学变形将和决策有关的变量和状态有关的变量分开，从而发现一些性质来优化动态规划。第37页，共48页，2023年，2月20日，星期日2.4.1例题Triangles(POI07-08StageIII)给定平面上N<1000个点，则显然会构成N(N-1)(N-2)/3个三角形求所有这些三角形的面积和第38页，共48页，2023年，2月20日，星期日2.4.1.1预备知识首先必须要知道叉积……向量a=(x1,y1)，b=(x2,y2)则有：a×b=x1*y2–x2*y1=|a||b|sinΘΘ为有向角度因此只要保证方向为正，那么向量a和b组成的三角形面积即为(a×b)/2第39页，共48页，2023年，2月20日，星期日2.4.1.2分析首先我们花O(N)的时间枚举左下角c所有需要计算的点都以点c为原点建系假设坐标为x[i]和y[i]按极角排序后，我们要求的就是不难得出一个O(N3)的算法第40页，共48页，2023年，2月20日，星期日2.4.1.3优化我们给式子做一个变形我们用Sy[i]记录y[i]到y[N]的和，Sx[i]记录x[i]到x[N]的和，那么要求的就是注意此时i和j这两个参数相互分离！第41页，共48页，2023年，2月20日，星期日2.5单调性这是很难的一部分内容，个人认为，如果是把目标放在NOIP级别的比赛，是不用掌握这部分内容的。但是，本着更高更快更强的精神：为了未来我们那崇高的理想！我们不应该着眼于现在！不要为现在而伤感，要相信自己！为了传递这份精神，还是浅浅谈一下第42页，共48页，2023年，2月20日，星期日2.5.1四边形不等式权函数w(i,j)，对于i≤i’<j≤j’如果满足w(i’,j)≤w(i,j’)则称w满足区间单调性如果满足