树状动态规划精品文稿.ppt

《树状动态规划精品文稿.ppt》由会员分享，可在线阅读，更多相关《树状动态规划精品文稿.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、树状动态规划第1页，本讲稿共34页DP在在NOI中中地地位位|表中按照较优算法标准分类的话，大致可分为五类，分别是表中按照较优算法标准分类的话，大致可分为五类，分别是|数据结构类：树的遍历，最短路径，并查集，树状数组，哈希表，博弈树；数据结构类：树的遍历，最短路径，并查集，树状数组，哈希表，博弈树；|数学分析类：初等数论，解方程，逻辑推理，组合分析，线性代数；数学分析类：初等数论，解方程，逻辑推理，组合分析，线性代数；|搜索类：宽度优先搜索，回溯法；搜索类：宽度优先搜索，回溯法；|动态程序设计类；动态程序设计类；|网络流类网络流类|面临的实际问题千奇百怪、数据模型千姿百态，求解方法千变万化。面

2、临的实际问题千奇百怪、数据模型千姿百态，求解方法千变万化。要求选手要求选手“阵而后战，兵法之常，运用之妙，存乎一心阵而后战，兵法之常，运用之妙，存乎一心”。竞竞赛赛数据数据结构结构数学数学分析分析动态程动态程序设计序设计搜索搜索网络流网络流累计累计NOIP2338NOI21216CSOI121116IOI4116累计累计9763126第2页，本讲稿共34页知知识识点点回回顾顾|是一个是一个“多阶段最优化决策的过程多阶段最优化决策的过程”。即由初始状态。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完

3、成整个这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线过程的一条最优的活动路线。状态状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。阶段阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。第3页，本讲稿共34页知知识识点点回回顾顾决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设：fk(i)k阶段状态

4、i的最优权值，即初始状态至状态i的最优代价：fk+1(i)=minxk(j)+u(i,j)|DP应该包含状态、阶段、决策、状态转移方程几种基本关系与属性。由于是按照阶段的顺序，直接在子问题最优解的基础上计算的，“不做已经做过的工作”，因此其效率比搜索法好得多。只要问题的计算过程呈阶段性，且可找到状态转移方程，我们宁可摒弃传统的搜索而采用动态程序设计方法。第4页，本讲稿共34页知知识识点点回回顾顾|是指它要么是一棵空树，要么它的是指它要么是一棵空树，要么它的左子树的所有结点比根结点小，右左子树的所有结点比根结点小，右子树的所有结点比树根结点大，它子树的所有结点比树根结点大，它的左子树和右子树分别

5、是一棵排序的左子树和右子树分别是一棵排序二叉树。二叉树。|最大排序二叉树是指在所有的排序最大排序二叉树是指在所有的排序二叉树中节点最多的一棵树。二叉树中节点最多的一棵树。第5页，本讲稿共34页知知识识点点回回顾顾根据关健码值直接访问。把关键码映射到表中的根据关健码值直接访问。把关键码映射到表中的一个位置来访问记录的过程。这个映射函数叫做哈希一个位置来访问记录的过程。这个映射函数叫做哈希函数，在存放记录的表叫做哈希表。也就是说，将所函数，在存放记录的表叫做哈希表。也就是说，将所有元素存储在一张表中，每一个元素具有一个哈希函有元素存储在一张表中，每一个元素具有一个哈希函数，按照如下两种方式给同一个

6、哈希函数值的所有元数，按照如下两种方式给同一个哈希函数值的所有元素分配多个空间素分配多个空间 哈希表（HashTable）第6页，本讲稿共34页知知识识点点回回顾顾考虑哈希函数的因素有：考虑哈希函数的因素有：|计算哈希函数所需时间；计算哈希函数所需时间；|关键字的长度；关键字的长度；|哈希表的大小；哈希表的大小；|关键字的分布情况；关键字的分布情况；|记录的查找频率。记录的查找频率。|可以经过较少的次数得到所查的可以经过较少的次数得到所查的元素，提高查询的时间效率。元素，提高查询的时间效率。第7页，本讲稿共34页知知识识点点回回顾顾|四边形不等式是四边形不等式是DonaldE.Knuth从最优

7、从最优二叉搜索树的数据结构中提出的。当函数二叉搜索树的数据结构中提出的。当函数wi,j满足：满足：时，称时，称w满足四边形不等式。满足四边形不等式。|在动态规划中被运用于证明决策的单调性。在动态规划中被运用于证明决策的单调性。第8页，本讲稿共34页知知识识点点回回顾顾二叉搜索树可以实现任何一种基二叉搜索树可以实现任何一种基本的动态集合操作，但当树的高度时，本的动态集合操作，但当树的高度时，这些操作性能可能变差，即不能保证这些操作性能可能变差，即不能保证在最坏的情况下动态集合操作的时间在最坏的情况下动态集合操作的时间为为O(lgn)。这样情况是因为二叉树可。这样情况是因为二叉树可能变得不平衡。用

8、一组规则让二叉树能变得不平衡。用一组规则让二叉树平衡起来，例如，红黑树确保了没平衡起来，例如，红黑树确保了没有一条路径会比任何其他路径长到两有一条路径会比任何其他路径长到两倍，因而基本上是平衡的。倍，因而基本上是平衡的。AVL树应树应用平衡化旋转规则来完成指针结构的用平衡化旋转规则来完成指针结构的修改。修改。第9页，本讲稿共34页知知识识点点回回顾顾如果将初始状态作为根结点，把从初如果将初始状态作为根结点，把从初始状态的每一个可能棋步出发，进行一轮始状态的每一个可能棋步出发，进行一轮游戏后得到的所有子状态作为根结点的孩游戏后得到的所有子状态作为根结点的孩子结点；然后从这些新状态出发进行下一子结

9、点；然后从这些新状态出发进行下一轮游戏，得到的又一批子状态作为新状态轮游戏，得到的又一批子状态作为新状态的孩子结点，的孩子结点，依次类推，就可以根据，依次类推，就可以根据游戏规则产生一棵包罗了各种可能状态变游戏规则产生一棵包罗了各种可能状态变化的树，习惯上称为博弈树化的树，习惯上称为博弈树 第10页，本讲稿共34页知知识识点点回回顾顾|奇数层的状态由先行方进行操作，偶数层的状态由后行方奇数层的状态由先行方进行操作，偶数层的状态由后行方进行操作；进行操作；|从根结点到当前状态的走步序列（路径）表示了双方依次轮流走过的从根结点到当前状态的走步序列（路径）表示了双方依次轮流走过的棋步；棋步；|叶子是

10、游戏的终止状态（即状态数为叶子是游戏的终止状态（即状态数为0或先前确定了取珠的洞或先前确定了取珠的洞口）。若叶子处在奇数层，后行方赢；若叶子处在偶数层，口）。若叶子处在奇数层，后行方赢；若叶子处在偶数层，先行方赢；先行方赢；|在对弈中，双方都想赢，都会采取取胜的策略。在对弈中，双方都想赢，都会采取取胜的策略。|我们在博弈树的每个结点上标一个值我们在博弈树的每个结点上标一个值F，由这个值来确定操作方最，由这个值来确定操作方最佳的走法。不妨认为，佳的走法。不妨认为，F越大对先行方越有利，奇数层结点总是挑选越大对先行方越有利，奇数层结点总是挑选使得值最大的方案走；而偶数层结点则恰好相反。由于子结点是

11、由使得值最大的方案走；而偶数层结点则恰好相反。由于子结点是由父结点推出来的，故父结点的值与其所有子结点的值有一定的关父结点推出来的，故父结点的值与其所有子结点的值有一定的关系。另一方面，游戏愈接近结束愈便于分析，也便于计算值。我们系。另一方面，游戏愈接近结束愈便于分析，也便于计算值。我们可从叶子结点出发，往上倒推每个结点的值，直至初始状态的值可从叶子结点出发，往上倒推每个结点的值，直至初始状态的值为止。整棵博弈树建立之后，便产生出取胜的策略。为止。整棵博弈树建立之后，便产生出取胜的策略。第11页，本讲稿共34页树树状状动动规规|某公司要举办一次晚会，但是某公司要举办一次晚会，但是为了使得晚会的

12、气氛更加活跃，为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在每个参加晚会的人都不希望在晚会中见到他的上司，要不然晚会中见到他的上司，要不然他们会很扫兴。现在已知每个他们会很扫兴。现在已知每个人的活跃指数和上司关系（当人的活跃指数和上司关系（当然不可能存在环），求邀请哪然不可能存在环），求邀请哪些人来能使得晚会的总活跃指些人来能使得晚会的总活跃指数最大。数最大。第12页，本讲稿共34页树树状状动动规规|按照要求构建一张关系图，可按照要求构建一张关系图，可见这是一棵树。对于这类最值见这是一棵树。对于这类最值问题，向来是用动态规划求解问题，向来是用动态规划求解的。的。|任何一个点的取舍可以看

13、作一任何一个点的取舍可以看作一种决策，那么状态就是在某个种决策，那么状态就是在某个点取的时候或者不取的时候，点取的时候或者不取的时候，以他为根的子树能有的最大活以他为根的子树能有的最大活跃总值。分别可以用跃总值。分别可以用fi,1和和fi,0表示。表示。第13页，本讲稿共34页树树状状动动规规|当这个点取的时候，他的所有当这个点取的时候，他的所有儿子都不能取，所以儿子都不能取，所以fi,1:=sum(fj,0,j为为i的儿子的儿子)i的权值。的权值。|不取的时候，他的所有儿子取不取的时候，他的所有儿子取不取无所谓，不过当然应该取不取无所谓，不过当然应该取价值最大的一种情况。所以价值最大的一种情

14、况。所以fi,0:=sum(max(fj,1,fj,0),j为为i的的i儿子）。儿子）。|这就是树状动规的基本形态。这就是树状动规的基本形态。第14页，本讲稿共34页树树状状动动规规|大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。|每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，数据结构必须在选修了高级语言程序设计之后才能选修。我们称高级语言程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的

15、先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，。第15页，本讲稿共34页树树状状动动规规|下面举例说明|上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。|学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。第16页，本讲稿共34页树树状状动动规规|输入输入 输入文件的第一行包括两个正整数M、N（中间用一 个 空 格 隔 开）其 中 M表 示 待 选 课 程 总 数（

16、1M1000)，N表示学生可以选的课程总数（1NM)。以下M行每行代表一门课，课号依次为1，2M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。|输出输出 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。第17页，本讲稿共34页树树状状动动规规7 42 20 10 42 17 17 62 2表12157346图202157346图1样例分析样例分析第18页，本讲稿共34页树树状状动动规规|们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为

17、根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？|我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：|可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。分析分析第19页，本讲稿共34页树树状状动动规规|转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。|我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前

18、一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3第20页，本讲稿共34页树树状状动动规规1=i=m,1=j=n,0=kj|这个方程的时间复杂度最大为n3，十分优秀了。|在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解 转移方程第21页，本讲稿共34页问问题题研研究究例例1、货物储运问题、货物储运问题单调性的确定第22页，本讲稿共34页在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用

19、最少。设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法第23页，本讲稿共34页货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于 ,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即四边形不等式第24页，本讲稿共34页四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，

20、当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而 s(i,j)s(i,j+1)s(i+1,j+1)，i j改进后算法所需的计算时间为 第25页，本讲稿共34页问问题题研研究究例例2LOSTCITY用哈希表、检索树优化DP第26页，本讲稿共34页问问题题研研究究例例3、排序二叉树、排序二叉树状态的存储第27页，本讲稿共34页问问题题研研究究例例4、取分（博弈树与、取分（博弈树与DP）博弈树与DP第28页，本讲稿共34页总总结结|动态规划有很多东西还需要我们动态规划有很多东西还需要我们更加努力地去探索和学习更加努力地去探索和学习.总体总体上说来上说来,动态规划是个既简单又动态规划是个

21、既简单又不简单的算法不简单的算法,熟练地掌握了动熟练地掌握了动态规划态规划,也就熟练地控制了比赛也就熟练地控制了比赛.第29页，本讲稿共34页练练习习题题|垃圾陷阱（垃圾陷阱（USACO&TJU1087）|卡门卡门农夫约翰极其珍视的一条农夫约翰极其珍视的一条Holsteins奶牛奶牛已经落了到已经落了到“垃圾井垃圾井”中。中。“垃圾井垃圾井”是农夫们扔垃圾的地方，它的深度为是农夫们扔垃圾的地方，它的深度为D(2=D=100)英尺。卡门想把垃圾堆起来，英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的

22、另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间道了每个垃圾扔下的时间t(0 t=1000)，以及每个垃圾堆放的高度，以及每个垃圾堆放的高度h(1=h=25)和吃进该垃圾能维持生命的时间和吃进该垃圾能维持生命的时间f(1=f=30)，要求出卡门最早能逃出井外的时间，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续假设卡门当前体内有足够持续10小时的能量，小时的能量，如果卡门如果卡门10小时内没有进食，卡门就将饿死

23、。小时内没有进食，卡门就将饿死。第30页，本讲稿共34页练练习习题题|字符串距离（字符串距离（TJU1086）|设有字符串设有字符串X，我们称在，我们称在X的头尾及中间插入任意多个空的头尾及中间插入任意多个空格后构成的新字符串为格后构成的新字符串为X的扩展串，如字符串的扩展串，如字符串X为为“abcbcd”，则字符串，则字符串“abcbcd”，“abcbcd”和和“abcbcd”都是都是X的扩展串，的扩展串，这里这里“”代表空格字符。代表空格字符。如果如果A1是字符串是字符串A的扩展串，的扩展串，B1是字符串是字符串B的扩展串，的扩展串，A1与与B1具有相同的长度，那么我具有相同的长度，那么我

24、们定义字符串们定义字符串A1与与B1的距离为相应位置上的字符的距离总和，的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的而两个非空格字符的距离定义为它们的ASCII码的差的绝对码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为空格字符与空格字符的距离为O。在字符串。在字符串A、B的所有扩展的所有扩展串中，必定存在两个等长的扩展串串中，必定存在两个等长的扩展串A1、B1，使得，使得A1与与B1之之间的距离达到最小，我们将这一距离定义为字符串间的距离达到最小，我们将这一距离定义为字符串

25、A、B的距的距离。离。请你写一个程序，求出字符串请你写一个程序，求出字符串A、B的距离。的距离。第31页，本讲稿共34页练练习习题题|二叉苹果树（二叉苹果树（Ural1018Ural1018）|有一棵苹果树，如果树枝有分叉，一定是分有一棵苹果树，如果树枝有分叉，一定是分2 2叉（就是说没有只有叉（就是说没有只有1 1个儿子的结点）个儿子的结点）这棵树共有这棵树共有N N个结点（叶子点或者树枝分叉个结点（叶子点或者树枝分叉点），编号为点），编号为1-N,1-N,树根编号一定是树根编号一定是1 1。我们用一根树枝两端连接的结点的编号来描我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是

26、一颗有述一根树枝的位置。下面是一颗有4 4个树枝个树枝的树的树2 2 5 5/3 3 4 4/1 1现在这颗树枝条太多了，需要剪枝。但是一现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住给定需要保留的树枝数量，求出最多能留住多少苹果。多少苹果。第32页，本讲稿共34页练练习习题题|最最长长前前缀缀IOI96&USACO1.4.3）|在生物学中，一些生物的在生物学中，一些生物的结结构是用包含其要构是用包含其要素的大写字母序列来表示的。生物学家素的大写字母序列来表示的。生物学家对对于于把把长长的序列分解成的序列分解成较较短的（称之短的

27、（称之为为元素的）元素的）序列很感序列很感兴兴趣。如果一个集合趣。如果一个集合P中的元素可中的元素可以通以通过过串串联组联组成一个序列成一个序列S，那么我，那么我们认为们认为序列序列S可以分解可以分解为为P中的元素。并不是所有中的元素。并不是所有的元素都必的元素都必须须出出现现。举举个例子，序列个例子，序列ABABACABAAB可以分解可以分解为为下面集合中的下面集合中的元素：元素：A,AB,BA,CA,BBC序列序列S的前面的前面K个字符称作个字符称作S中中长长度度为为K的前的前缀缀。设计设计一一个程序，个程序，输输入一个元素集合以及一个大写字入一个元素集合以及一个大写字母序列，母序列，计计

28、算算这这个序列最个序列最长长的前的前缀缀的的长长度。度。第33页，本讲稿共34页练练习习题题|祝福（祝福（TJU1078）|得知得知Atlantis即将沉没的消息以后，即将沉没的消息以后，King决定把他的人决定把他的人民送到安全的国外去。但是码头已经废弃很多很多年了。民送到安全的国外去。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了这个迷宫码头前有一个迷宫，国王的骑士只身闯入了这个迷宫 骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招架不住了，他的大马被打得奄奄一息（。战，所以很快便招架不住了，

29、他的大马被打得奄奄一息（。）这个时候，迷宫中的两座石像）这个时候，迷宫中的两座石像(一个是猫老大，一个是天使。一个是猫老大，一个是天使。（！（！)里放出了无数锋利的刀片，把不明生物全部杀里放出了无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒指，上面写着：了一个戒指，上面写着：“这个戒指会帮助你逃脱。它赋这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要予了神奇的力量。有了它，每次移动如果是只要|x-x1|+|y-y1|(x1,y1)的移动！的移动！”(Angel暗自想：还有这么心黑的暗自想：还有这么心黑的)迷宫为迷宫为n*m的的矩阵。骑士从矩阵。骑士从(n,m)到到(1,1)。问：在戒指的帮助下，。问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提下，骑士最少要多少步才能回到入口？在步数最少的前提下，总共有多少种办法到达入口？注意，骑士不会傻到一直总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。停留在原地不动。第34页，本讲稿共34页