树状动态规划

树状动态规划第一页，共三十四页，2022年，8月28日DP在NOI中地位表中按照较优算法标准分类的话，大致可分为五类，分别是数据结构类：树的遍历，最短路径，并查集，树状数组，哈希表，博弈树；数学分析类：初等数论，解方程，逻辑推理，组合分析，线性代数；搜索类：宽度优先搜索，回溯法；动态程序设计类；网络流类面临的实际问题千奇百怪、数据模型千姿百态，求解方法千变万化。要求选手“阵而后战，兵法之常，运用之妙，存乎一心”。

竞赛数据结构数学分析动态程序设计搜索网络流累计NOIP2338NOI21216CSOI12111`6IOI4116累计9763126第二页，共三十四页，2022年，8月28日知识点回顾是一个“多阶段最优化决策的过程”。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。动态规划⑴状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。⑵阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。第三页，共三十四页，2022年，8月28日知识点回顾⑶决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。⑷状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设：fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价：fk+1(i)=min{xk(j)+u(i,j)}DP应该包含状态、阶段、决策、状态转移方程几种基本关系与属性。由于是按照阶段的顺序，直接在子问题最优解的基础上计算的，“不做已经做过的工作”，因此其效率比搜索法好得多。只要问题的计算过程呈阶段性，且可找到状态转移方程，我们宁可摒弃传统的搜索而采用动态程序设计方法。第四页，共三十四页，2022年，8月28日知识点回顾是指它要么是一棵空树，要么它的左子树的所有结点比根结点小，右子树的所有结点比树根结点大，它的左子树和右子树分别是一棵排序二叉树。最大排序二叉树是指在所有的排序二叉树中节点最多的一棵树。排序二叉树二叉搜索树二叉检索树二分检索树第五页，共三十四页，2022年，8月28日知识点回顾

根据关健码值直接访问。把关键码映射到表中的一个位置来访问记录的过程。这个映射函数叫做哈希函数，在存放记录的表叫做哈希表。也就是说，将所有元素存储在一张表中，每一个元素具有一个哈希函数，按照如下两种方式给同一个哈希函数值的所有元素分配多个空间

哈希表（HashTable）第六页，共三十四页，2022年，8月28日知识点回顾考虑哈希函数的因素有：计算哈希函数所需时间；关键字的长度；哈希表的大小；关键字的分布情况；记录的查找频率。可以经过较少的次数得到所查的元素，提高查询的时间效率。

第七页，共三十四页，2022年，8月28日知识点回顾四边形不等式是DonaldE.Knuth从最优二叉搜索树的数据结构中提出的。当函数w[i,j]满足：时，称w满足四边形不等式。在动态规划中被运用于证明决策的单调性。四边形不等式第八页，共三十四页，2022年，8月28日知识点回顾二叉搜索树可以实现任何一种基本的动态集合操作，但当树的高度时，这些操作性能可能变差，即不能保证在最坏的情况下动态集合操作的时间为O(lgn)。这样情况是因为二叉树可能变得不平衡。用一组规则让二叉树平衡起来，例如，红－黑树确保了没有一条路径会比任何其他路径长到两倍，因而基本上是平衡的。AVL树应用平衡化旋转规则来完成指针结构的修改。

平衡二叉树第九页，共三十四页，2022年，8月28日知识点回顾如果将初始状态作为根结点，把从初始状态的每一个可能棋步出发，进行一轮游戏后得到的所有子状态作为根结点的孩子结点；然后从这些新状态出发进行下一轮游戏，得到的又一批子状态作为新状态的孩子结点，…，依次类推，就可以根据游戏规则产生一棵包罗了各种可能状态变化的树，习惯上称为博弈树

博弈树第十页，共三十四页，2022年，8月28日知识点回顾奇数层的状态由先行方进行操作，偶数层的状态由后行方进行操作；从根结点到当前状态的走步序列（路径）表示了双方依次轮流走过的棋步；叶子是游戏的终止状态（即状态数为0或先前确定了取珠的洞口）。若叶子处在奇数层，后行方赢；若叶子处在偶数层，先行方赢；在对弈中，双方都想赢，都会采取取胜的策略。我们在博弈树的每个结点上标一个值F，由这个值来确定操作方最佳的走法。不妨认为，F越大对先行方越有利，奇数层结点总是挑选使得Ｆ值最大的方案走；而偶数层结点则恰好相反。由于子结点是由父结点推出来的，故父结点的Ｆ值与其所有子结点的Ｆ值有一定的关系。另一方面，游戏愈接近结束愈便于分析，也便于计算Ｆ值。我们可从叶子结点出发，往上倒推每个结点的Ｆ值，直至初始状态的Ｆ值为止。整棵博弈树建立之后，便产生出取胜的策略。博弈树的特征构造博弈树的基本思想第十一页，共三十四页，2022年，8月28日树状动规某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的上司，要不然他们会很扫兴。现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人来能使得晚会的总活跃指数最大。back没有上司的晚会第十二页，共三十四页，2022年，8月28日树状动规按照要求构建一张关系图，可见这是一棵树。对于这类最值问题，向来是用动态规划求解的。任何一个点的取舍可以看作一种决策，那么状态就是在某个点取的时候或者不取的时候，以他为根的子树能有的最大活跃总值。分别可以用f[i,1]和f[i,0]表示。back第十三页，共三十四页，2022年，8月28日树状动规当这个点取的时候，他的所有儿子都不能取，所以f[i,1]:=sum(f[j,0],j为i的儿子)＋i的权值。不取的时候，他的所有儿子取不取无所谓，不过当然应该取价值最大的一种情况。所以f[i,0]:=sum(max(f[j,1],f[j,0]),j为i的i儿子）。这就是树状动规的基本形态。back第十四页，共三十四页，2022年，8月28日树状动规大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。选课第十五页，共三十四页，2022年，8月28日树状动规下面举例说明上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。第十六页，共三十四页，2022年，8月28日树状动规

输入输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。输出输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。第十七页，共三十四页，2022年，8月28日树状动规7422010421717622表12157346图202157346图1样例分析第十八页，共三十四页，2022年，8月28日树状动规们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。分析第十九页，共三十四页，2022年，8月28日树状动规转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3改造树第二十页，共三十四页，2022年，8月28日树状动规1<=i<=m,1<=j<=n,0<=k<j这个方程的时间复杂度最大为n3，十分优秀了。在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解转移方程第二十一页，共三十四页，2022年，8月28日问题研究例1、货物储运问题back单调性的确定第二十二页，共三十四页，2022年，8月28日在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并a[i:j]，1≤i≤j≤n，所需的最少费用为m[i,j]，则原问题的最优值为m[1，n]。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法货物储运第二十三页，共三十四页，2022年，8月28日货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足时称W关于区间包含关系单调

对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即四边形不等式第二十四页，共三十四页，2022年，8月28日四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而s(i,j)s(i,j+1)s(i+1,j+1)，ij改进后算法所需的计算时间为第二十五页，共三十四页，2022年，8月28日问题研究例2LOSTCITY用哈希表、检索树优化DP第二十六页，共三十四页，2022年，8月28日问题研究例3、排序二叉树back状态的存储第二十七页，共三十四页，2022年，8月28日问题研究例4、取分（博弈树与DP）博弈树与DP第二十八页，共三十四页，2022年，8月28日总结动态规划有很多东西还需要我们更加努力地去探索和学习.总体上说来,动态规划是个既简单又不简单的算法,熟练地掌握了动态规划,也就熟练地控制了比赛.back第二十九页，共三十四页，2022年，8月28日练习题垃圾陷阱（USACO&TJU1087）卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2<=D<=100)英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间t(0<t<=1000)，以及每个垃圾堆放的高度h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。第三十页，共三十四页，2022年，8月28日练习题字符串距离（TJU1086）设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。第三十一页，共三十四页，2022年，8月28日练习题二叉苹果树（Ural1018）有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2

5

\/

3

4

\/

1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。第三十二页，共三十四页，2022年，8月28日练习题最长前缀IOI'96&USACO1.4.3）在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。如果一个集合P中的元素可以通过串联组成一个序列S