oip教程动态规划.ppt

动态规划,陈爽,为了解决一类最优化问题 通过求得所有子问题的最优解来得到最终问题的最优解,动态规划,状态 状态转移方程 初始条件,动态规划的基本要素,线性动态规划 区间动态规划 状态压缩动态规划 树形动态规划,动态规划的分类,状态是一维的 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的上升序列的个数 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都在数列中出现了恰好一次。 在这个数列中从左到右任取两个数，如果前者比后者大，那么这对数就是一个逆序对。而整个数列的逆序数就是其中所有逆序对的总数。例如，数列（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-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不可滥用 用之前先考虑是否符合最优化原理，并且没有后效性 确定了是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,贪心,用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,在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数=1000,例5. 关灯问题,关掉的灯一定是一个连续的区间 如果路过一个灯但是没有去关掉它 设 optij0/1 表示区间i,j中的灯都被关掉之后的最小损失，最后一维表示小朋友的当前位置 转移：考虑当前的关灯操作 时间复杂度：O(N2),Solution,设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：,例6. 加分二叉树（NOIP2003）,subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。,Solution,注意到任意一棵子树的中序遍历一定是一段连续的区间 枚举区间中的第几个元素作为这一段区间的根 记fij表示中序遍历为i,j这个区间的子树的最大分数，gi表示第i个点的分数 Fij=max(Fik-1*Fk+1j+gi) 初始条件：Fij=0,Solution,给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。 矩形边长小于等于100,例7. 矩形分割问题,Fij表示长为i宽为j的矩形所需的最小正方形个数 Fij=min(Fik+Fij-k,Fkj+Fi-kj),Solution,见外部题目描述,例8. psolve,状态：Fij表示ij在一个月做完的最小所需月份 枚举上一个做了ki-1 转移方程：Fij=min(Fki-1+1), s1ij+s2ki-1=P, 且Fki-1合法 初始条件：F00=1 此题写起来有好多小细节，建议练习代码,Solution,动态规划问题具有以下基本特征： 1、问题具有多阶段决策的特征。 2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。 3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。 4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。,动态规划的基本模型,状态压缩是一种非常暴力的动态规划，特征也非常明显，一般适用于数据规模较小的情况。 状态压缩复杂度通常情况下是是指数级的，编程复杂度也相对较大。 所谓状态压缩，就是把一个比较复杂的状态压缩为一个数，通常采用某一种进制的表示方法 经常通过记忆化搜索来实现,Part 3. 状态压缩动态规划,放寒假了，小D终于可以回家了。一个学期之后他有太多的东西想带回家。 小D的背包可以被看作一个4行N列的矩阵，每个物品放入背包的物品恰好需要占据两个相邻的方格，任意两个物品不能占据相同的方格。为了充分的利用自己的背包，小D希望背包的所有空间都放置了物品，也就是说，背包中恰好放入了2N个物品。 现在小D想知道，不同的放置方案数有多少种。,例9. 多米诺骨牌覆盖,搜索？ n很大，超时严重 动态规划？ 如何表示状态？ 注意到每一列最多只有4行，每一个格子对下一行的影响只有2种：下一行对应的格子是否可以和当前格子一起放进一个物品 状态压缩！0/1表示每个格子的状态，4位二进制数表示一行的状态,Solution,用FkS来描述一个状态，这个状态表示已经把矩阵的前k-1列全部放满，并且第k列的覆盖情况为S（s为一个4位二进制数），此时的摆放方案数（注意，其实只有S中1的个数为偶数时状态才有意义，更加深入的探讨会发现需要使用的状态很少）。 通过枚举第k列骨牌的放置方案，不难得到从Fku（u = 0 15）到Fk+1v（v = 0 15 ）的转移方程。这个过程需要另外写一个程序去枚举才能完成。,Solution,L盏灯，每盏灯为0/1，表示亮的或暗的 有一个叉子有T个叉尖，相邻两个叉尖的距离等于相邻两盏灯的距离。有些叉尖断了，用0表示，否则为1 叉子对准开关，可以改变灯的状态 已知初始灯的状态和叉尖状态，求叉尖操作的序列使得最后亮着的灯最少 L=50, T=7,例10.xlite,同一位置只可能操作一次 可以从左到右依次操作 FiS表示最后T盏灯灯的状态为S时，前i盏灯至少