noip教程-动态规划.ppt

《noip教程-动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划陈爽为了解决一类最优化问题通过求得所有子问题的最优解来得到最终问题的最优解动态规划状态状态转移方程初始条件动态规划的基本要素线性动态规划区间动态规划状态压缩动态规划树形动态规划动态规划的分类状态是一维的F[i]由F[j](j

2、求本质不同的长度为N的上升序列的个数N<=1000例1.最长上升序列状态：F[i]表示以b[i]结尾的最长上升序列长度转移方程：F[i]=max(F[j]+1),jB[j]初始条件：T[i]=1Solution本质不同？Order[i]表示B[i]在序列B中是第几大的T[i]=sigma(T[j]),当某个order[j1]=order[j2]时，只累加一

3、个时间复杂度：O(N^2)空间复杂度：O(N)SolutionP[i]表示上身序列长度为i的序列末尾元素的最小值当计算F[i]时，二分j，满足P[j]

4、），（4，2）和（3，2）。写一个程序，计算有多少长度为N的这种数列，使它的逆序数恰为C。N<=1000,C<=10000例2.zbrka状态：F[i][j]表示1～i的一个排列，逆序对数目为j的方案数枚举1的位置F[i][j]=sigma(F[i-1][j-k]),0<=k<=i-1时间复杂度：O(N*N*C)空间复杂度：O(N*C)SolutionF[i][j]=F[i][j-1]+F[i-1][j]-F[i-1][j-i]第i阶段只与第i-1阶段有关滚动数组，省掉一维时间复杂度：O(N*C)空间复杂度：O(C)Solution如

5、图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。例3.Mod4余数最小问题状态：F[i]表示到点i的最小值转移：F[i]=min((F[j]+num[i])mod4),j到i有边样例就出现bugQuestions局部最优解不能保证全局最优解本题不符合最优化性质F[i][j]表示到点i余数为j是否可行求出所有x=(F[k][p]+num[i])%4,F[i][x]=trueSolutionDP不可滥用用之前先考虑是否符合最优化原理，并且没有后效性确定了是DP之后考虑三个基本

6、要素Summary状态有两维或者多维F[i][j]表示i~j这个区间的最优值F[i-1][j],F[i][j-1]F[i][j]F[i][k]+F[k][j]F[i][j]Part2.区间动态规划在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大例4.石子合

7、并Example贪心N=5，石子数分别为346542用贪心法的合并过程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24总分：62第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24总分：61显然，贪心法是错误的。用data[i,j]表示合并第i～j颗石子的分值状态：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<

8、=j)初始条件：max[i,1]=0状态：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)初始条件：min[i,0]=