noip教程动态规划课件

,Click to edit Master title style,2019/1/25,#,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,为了解决一类最优化问题,通过求得所有子问题的最优解来得到最终问题的最优解,动态规划,为了解决一类最优化问题动态规划,1,状态,状态转移方程,初始条件,动态规划的基本要素,状态动态规划的基本要素,2,线性动态规划,区间动态规划,状态压缩动态规划,树形动态规划,动态规划的分类,线性动态规划动态规划的分类,3,状态是一维的,Fi,由,F,j,(ji),得到,初始条件,F0,或,F1,Part 1,线性动态规划,状态是一维的Part 1 线性动态规划,4,设有整数序列,b1,b2,b3,bm,，若存在下标,i1i2i3,in,，且,b,i1,b,i2,b,i3,b,in,，则称,b1,b2,b3,bm,中有长度为,n,的上升序列,b,i1,b,i2,b,i3,b,in,。,求最长上升序列的长度,N,求长度为,N,的上升序列的个数,求本质不同的长度为,N,的上升序列的个数,N=1000,例,1.,最长上升序列,设有整数序列b1,b2,b3,bm，若存在下标i1i2,5,状态：,Fi,表示以,bi,结尾的最长上,升,序列长度,转移方程：,Fi=max(Fj+1),jI,bjbi,初始条件：,Fi=1,1=iBj,初始条件：,Ti=1,Solution,状态：Fi表示以bi结尾的最长上升序列长度Solut,6,本质不同？,Orderi,表示,Bi,在序列,B,中是第几大的,Ti=sigma(Tj),当某个,o,rderj1=orderj2,时，只累加一个,时间复杂度：,O(N2),空间复杂度,：,O(N),Solution,本质不同？Solution,7,Pi,表示上身序列长度为,i,的序列末尾元素的最小值,当计算,Fi,时，二分,j,，满足,PjBi,Fi=Fj+1,PFi=min(PFi,Bi),时间复杂度：,O(NlogN),LIS O,（,NlogN,）算法,Pi 表示上身序列长度为i的序列末尾元素的最小值LIS,8,考虑一个由,N,个整数构成的数列，其中,1,到,N,都在数列中出现了恰好一次。,在这个数列中从左到右任取两个数，如果前者比后者大，那么这对数就是一个逆序对。而整个数列的逆序数就是其中所有逆序对的总数。例如，数列（,1,，,4,，,3,，,2,）的逆序数为,3,，因为存在三个逆序对：（,4,，,3,），（,4,，,2,）和（,3,，,2,）。,写一个程序，计算有多少长度为,N,的这种数列，使它的逆序数恰为,C,。,N=1000,C=10000,例,2.zbrka,考虑一个由N个整数构成的数列，其中1到N都在数列中出现了恰好,9,状态：,Fij,表示,1,i,的一个排列，逆序对数目为,j,的方案数,枚举,1,的位置,Fij=sigma(Fi-1j-k),0=k=i-1,时间复杂度：,O(N*N*C),空间复杂度：,O(N*C),Solution,状态：Fij表示1i的一个排列，逆序对数目为j的方,10,Fij=Fij-1+,Fi-1j-Fi-1j-i,第,i,阶段只与第,i-1,阶段有关,滚动数组，省掉一维,时间复杂度：,O(N*C),空间复杂度：,O(C),Solution,Fij=Fij-1+Fi-1j-F,11,如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以,4,的余数最小。,例,3.Mod 4,余数最小问题,如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（,12,状态：,Fi,表示到点,i,的最小值,转移：,Fi=min(Fj+numi)mod 4),j,到,i,有边,样例就出现,bug,Questions,状态：Fi表示到点i的最小值Questions,13,局部最优解不能保证全局最优解,本题不符合最优化性质,Fij,表示到点,i,余数为,j,是否可行,求出所有,x=(F,k,p+numi)%4,Fix=true,Solution,局部最优解不能保证全局最优解Solution,14,DP,不可滥用,用之前先考虑是否符合最优化原理，并且没有后效性,确定了是,DP,之后考虑三个基本要素,Summary,DP不可滥用Summary,15,状态有两维或者多维,Fij,表示,ij,这个区间的最优值,Fi-1j,Fij-1,Fij,Fik+Fkj,Fij,Part 2.,区间动态规划,状态有两维或者多维Part 2.区间动态规划,16,在一园形操场四周摆放,N,堆石子,(N100),现要将石子有次序地合并成一堆,.,规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数,N,及每堆石子数,(20),(1),选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最少,(2),选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最大,例,4.,石子合并,在一园形操场四周摆放N堆石子(N100),现要将石子有次序,17,Example,Example,18,贪心,N=5,，,石子数分别为,3 4 6 5 4 2,用贪心法的合并过程如下：,第一次,3 4 6 5 4 2,得分,5,第二次,5 4 6 5 4,得分,9,第三次,9 6 5 4,得分,9,第四次,9 6 9,得分,15,第五次,15 9,得分,24,第六次,24,总分：,62,第一次,3 4 6 5 4 2,得分,7,第二次,7 6 5 4 2,得分,13,第三次,13 5 4 2,得分,6,第四次,13 5 6,得分,11,第五次,13 11,得分,24,第六次,24,总分：,61,显然，贪心法是错误的。,贪心N=5，石子数分别为3 4 6 5 4 2用贪心法的合并,19,用,datai,j,表示合并第,i,j,颗石子的分值,状态：,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,用datai,j表示合并第ij颗石子的分值Soluti,20,在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数,=1000,例,5.,关灯问题,在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉,21,关掉的灯一定是一个连续的区间,如果路过一个灯但是没有去关掉它,设,optij0/1,表示区间,i,j,中的灯都被关掉之后的最小损失，最后一维表示小朋友的当前位置,转移：考虑当前的关灯操作,时间复杂度：,O(N2),Solution,关掉的灯一定是一个连续的区间Solution,22,设一个,n,个节点的二叉树,tree,的中序遍历为（,l,2,3,n,），其中数字,1,2,3,n,为节点编号。每个节点都有一个分数（均为正整数），记第,j,个节点的分数为,di,，,tree,及它的每个子树都有一个加分，任一棵子树,subtree,（也包含,tree,本身）的加分计算方法如下：,例,6.,加分二叉树（,NOIP2003,）,设一个n个节点的二叉树tree的中序遍历为（l,2,3,23,subtree,的左子树的加分,subtree,的右子树的加分,subtree,的根的分数,若某个子树为主，规定其加分为,1,，叶子的加分就是叶节点本身的分数。不考虑它的空子树。,试求一棵符合中序遍历为（,1,2,3,n,）且加分最高的二叉树,tree,。,Solution,subtree的左子树的加分 subtree的右子树的加分,24,注意到任意一棵子树的中序遍历一定是一段,连续,的区间,枚举区间中的第几个元素作为这一段区间的根,记,fij,表示中序遍历为,i,j,这个区间的子树的最大分数，,gi,表示第,i,个点的分数,Fij=max(Fik-1*Fk+1j+gi),初始条件：,Fi,j,=0,Solution,注意到任意一棵子树的中序遍历一定是一段连续的区间Soluti,25,给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。,矩形边长小于等于,100,例,7.,矩形,分割,问题,给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方,26,Fij,表示长为,i,宽为,j,的矩形所需的最小正方形个数,Fij=min(Fik+Fij-k,Fkj+Fi-kj),Solution,Fij表示长为i宽为j的矩形所需的最小正方形个数So,27,见外部题目描述,例,8.psolve,见外部题目描述例8.psolve,28,状态：,Fij,表示,i,j,在一个月做完的最小所需月份,枚举上一个做了,k,i-1,转移方程：,Fij=min(Fki-1+1),s1ij+s2ki-1=P,且,Fki-1,合法,初始条件：,F00=1,此题写起来有好多小细节，建议练习代码,Solution,状态：Fij表示ij在一个月做完的最小所需月份So,29,动态规划问题具有以下基本特征,：,1,、问题具有多阶段决策的特征。,2,、每一阶段都有相应的,“,状态,”,与之对应，描述状态的量称为,“,状态变量,”,。,3,、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。,4,、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。,动态规划的基本模型,动态规划问题具有以下基本特征：动态规划的基本模型,30,状态压缩是一种非常暴力的动态规划，特征也非常明显，一般适用于,数据规模较小,的情况。,状态压缩复杂度通常情况下是是指数级的，编程复杂度也相对较大。,所谓状态压缩，就是把一个比较复杂的状态压缩为一个数，通常采用某一种进制的表示方法,经常通过记忆化搜索来实现,Part 3.,状态压缩动态规划,状态压缩是一种非常暴力的动态规划，特征也非常明显，一般适用于,31,放寒假了，小,D,终于可以回家了。一个学期之后他有太多的东西想带回家。小,D,的背包可以被看作一个,4,行,N,列的矩阵，每个物品放入背包的物品恰好需要占据两个相邻的方格，任意两个物品不能占据相同的方格。为了充分的利用自己的背包，小,D,希望背包的所有空间都放置了物品，也就是说，背包中恰好放入了,2N,个物品。现在小,D,想知道，不同的放置方案数有多少种。,例,9.,多米诺骨牌覆盖,放寒假了，小D终于可以回家了。一个学期之后他有太多的东西想带,32,搜索？,n,很大，超时严重,动态规划？,如何表示状态？,注意到每一列最多只有,4,行，每一个格子对下一行的影响只有,2,种：下一行对应的格子是否可以和当前格子一起放进一个物品,状态压缩！,0/1,表示每个格子的状态，,4,位二进制数表示一行的状态,Solution,搜索？Solution,33,用,FkS,来描述一个状态，这个状态表示已经把矩阵的前,k-1,列全部放满，并且第,k,列的覆盖情况为,S,（,s,为一个,4,位二进制数），此时的摆放方案数（注意，其实只有,S,中,1,的个数为偶数时状态才有意义，更加深入的探讨会发现需要使用的状态很少）。,通过枚举第,k,列骨牌的放置方案，不难得到从,Fku,（,u=0 15,）到,Fk+1v,（,v=0 15,）的转移