noip教程--动态规划.ppt
《noip教程--动态规划.ppt》由会员分享,可在线阅读,更多相关《noip教程--动态规划.ppt(39页珍藏版)》请在三一文库上搜索。
1、动态规划,陈爽,为了解决一类最优化问题 通过求得所有子问题的最优解来得到最终问题的最优解,动态规划,状态 状态转移方程 初始条件,动态规划的基本要素,线性动态规划 区间动态规划 状态压缩动态规划 树形动态规划,动态规划的分类,状态是一维的 Fi 由 Fj (ji) 得到 初始条件 F0 或 F1,Part 1 线性动态规划,设有整数序列b1,b2,b3,bm,若存在下标i1i2i3 in,且bi1bi2bi3 bin,则称 b1,b2,b3,bm中有长度为n的上升序列bi1 , bi2 ,bi3 ,bin 。 求最长上升序列的长度N 求长度为N的上升序列的个数 求本质不同的长度为N的上升序列的
2、个数 N=1000,例1.最长上升序列,状态:Fi表示以bi结尾的最长上升序列长度 转移方程:Fi=max(Fj+1),jBj 初始条件:Ti=1,Solution,本质不同? Orderi表示Bi在序列B中是第几大的 Ti=sigma(Tj), 当某个orderj1=orderj2时,只累加一个 时间复杂度:O(N2) 空间复杂度:O(N),Solution,Pi 表示上身序列长度为i的序列末尾元素的最小值 当计算Fi时,二分j,满足PjBi Fi=Fj+1 PFi=min(PFi, Bi) 时间复杂度:O(NlogN),LIS O(NlogN)算法,考虑一个由N个整数构成的数列,其中1到N
3、都在数列中出现了恰好一次。 在这个数列中从左到右任取两个数,如果前者比后者大,那么这对数就是一个逆序对。而整个数列的逆序数就是其中所有逆序对的总数。例如,数列(1,4,3,2)的逆序数为3,因为存在三个逆序对:(4,3),(4,2)和(3,2)。 写一个程序,计算有多少长度为N的这种数列,使它的逆序数恰为C。 N=1000,C=10000,例2. zbrka,状态:Fij表示1i的一个排列,逆序对数目为j的方案数 枚举1的位置 Fij=sigma(Fi-1j-k),0=k=i-1 时间复杂度:O(N*N*C) 空间复杂度:O(N*C) ,Solution,Fij=Fij-1+Fi-1j-Fi-
4、1j-i 第i阶段只与第i-1阶段有关 滚动数组,省掉一维 时间复杂度:O(N*C) 空间复杂度:O(C),Solution,如图,已知一个有向图,求一条从最左边的点走到最右边点的方案(只能从左往右走),使得所经过的权值和除以4的余数最小。,例3. Mod 4 余数最小问题,状态:Fi表示到点i的最小值 转移:Fi=min(Fj+numi) mod 4),j到i有边 样例就出现bug ,Questions,局部最优解不能保证全局最优解 本题不符合最优化性质 Fij 表示到点i余数为j是否可行 求出所有x=(Fkp+numi)%4,Fix=true,Solution,DP不可滥用 用之前先考虑是
5、否符合最优化原理,并且没有后效性 确定了是DP之后考虑三个基本要素,Summary,状态有两维或者多维 Fij表示ij这个区间的最优值 Fi-1j,Fij-1 Fij Fik + Fkj Fij,Part 2.区间动态规划,在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少 (2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大,例4. 石子合并,Example,贪心,用
6、datai,j表示合并第ij颗石子的分值 状态:maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j) 初始条件:maxi,1 = 0 状态:mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j) 初始条件:mini,0 = 0 时间复杂度:O(N2),Solution,在一条马路上,有一排灯,一个小朋友要去关灯,如果灯没有被关掉,就会每秒造成一定的损失。小朋友一开始在某一个位置,在他左边和右边分别有一些灯,给出这些灯和他的距
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- noip 教程 动态 规划
链接地址:https://www.31doc.com/p-2202273.html