树状动态规划

《树状动态规划》由会员分享，可在线阅读，更多相关《树状动态规划（34页珍藏版）》请在金锄头文库上搜索。

1、树状 动态 规划DP在NOI中地位|表中按照较优算法标准分类的话，大致可分为五类，分 别是|数据结构类：树的遍历，最短路径，并查集，树状数组 ，哈希表，博弈树；|数学分析类：初等数论，解方程，逻辑推理，组合分析 ，线性代数；|搜索类：宽度优先搜索，回溯法；|动态程序设计类；|网络流类| 面临的实际问题千奇百怪、数据模型千姿百态，求解 方法千变万化。要求选手“阵而后战，兵法之常，运用之妙，存 乎一心”。 竞 赛数据 结构数学 分析动态程 序设计搜索网络流累计NOIP2338NOI21216CSOI121116IOI4116累计9763126知识点回顾|是一个“多阶段最优化决策的过程”。即由初始

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

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

4、根据关健码值直接访问。把关键码映 射到表中的一个位置来访问记录的过程。这个 映射函数叫做哈希函数，在存放记录的表叫做 哈希表。也就是说，将所有元素存储在一张表 中，每一个元素具有一个哈希函数，按照如下 两种方式给同一个哈希函数值的所有元素分配 多个空间 知识点回顾考虑哈希函数的因素有：|计算哈希函数所需时间；|关键字的长度；|哈希表的大小；|关键字的分布情况；|记录的查找频率。|可以经过较少的次数得到所查 的元素，提高查询的时间效率。 知识点回顾|四边形不等式是Donald E. Knuth从 最优二叉搜索树的数据结构中提出的。 当函数wi,j满足：时，称w满足四边形不等式。|在动态规划中被运

5、用于证明决策的 单调性。知识点回顾二叉搜索树可以实现任何一 种基本的动态集合操作，但当树的高 度时，这些操作性能可能变差，即不 能保证在最坏的情况下动态集合操作 的时间为O(lg n)。这样情况是因为二 叉树可能变得不平衡。用一组规则让 二叉树平衡起来，例如，红黑树确 保了没有一条路径会比任何其他路径 长到两倍，因而基本上是平衡的。 AVL树应用平衡化旋转规则来完成指 针结构的修改。 知识点回顾如果将初始状态作为根结点，把从 初始状态的每一个可能棋步出发，进行一 轮游戏后得到的所有子状态作为根结点的 孩子结点；然后从这些新状态出发进行下 一轮游戏，得到的又一批子状态作为新状 态的孩子结点，依次

6、类推，就可以根 据游戏规则产生一棵包罗了各种可能状态 变化的树，习惯上称为博弈树 知识点回顾|奇数层的状态由先行方进行操作，偶数层的状态由 后行方进行操作；|从根结点到当前状态的走步序列（路径）表示了双 方依次轮流走过的棋步；|叶子是游戏的终止状态（即状态数为0或先前确定 了取珠的洞口）。若叶子处在奇数层，后行方赢；若叶子 处在偶数层，先行方赢；|在对弈中，双方都想赢，都会采取取胜的策略。| 我们在博弈树的每个结点上标一个值F ，由这个值 来确定操作方最佳的走法。不妨认为，F 越大对先行方越 有利，奇数层结点总是挑选使得值最大的方案走；而偶 数层结点则恰好相反。由于子结点是由父结点推出来的，

7、故父结点的值与其所有子结点的值有一定的关系。另 一方面，游戏愈接近结束愈便于分析，也便于计算值。 我们可从叶子结点出发，往上倒推每个结点的值，直至 初始状态的值为止。整棵博弈树建立之后，便产生出取 胜的策略。树状动规|某公司要举办一次晚会，但 是为了使得晚会的气氛更加活跃 ，每个参加晚会的人都不希望在 晚会中见到他的上司，要不然他 们会很扫兴。现在已知每个人的 活跃指数和上司关系（当然不可 能存在环），求邀请哪些人来能 使得晚会的总活跃指数最大。 树状动规|按照要求构建一张关系图， 可见这是一棵树。对于这类最值 问题，向来是用动态规划求解的 。|任何一个点的取舍可以看作 一种决策，那么状态就是

8、在某个 点取的时候或者不取的时候，以 他为根的子树能有的最大活跃总 值。分别可以用fi,1和fi,0表示 。树状动规|当这个点取的时候，他的所 有儿子都不能取，所以 fi,1:=sum(fj,0, j为i的儿子) i的权值。|不取的时候，他的所有儿子 取不取无所谓，不过当然应该取 价值最大的一种情况。所以 fi,0:=sum(max(fj,1,fj,0), j 为i的i儿子）。|这就是树状动规的基本形态 。树状动规|大学里实行学分。每门课程都有一定的学 分，学生只要选修了这门课并考核通过就能获 得相应的学分。学生最后的学分是他选修的各 门课的学分的总和。|每个学生都要选择规定数量的课程。其中

9、有些课程可以直接选修，有些课程需要一定的 基础知识，必须在选了其它的一些课程的基础 上才能选修。例如，数据结构必须在选修 了高级语言程序设计之后才能选修。我们 称高级语言程序设计是数据结构的先 修课。每门课的直接先修课最多只有一门。两 门课也可能存在相同的先修课。为便于表述每 门课都有一个课号，课号依次为1，2，3， 。 树状动规|下面举例说明|上例中1是2的先修课，即如果要选修2， 则1必定已被选过。同样，如果要选修3，那么1 和2都一定已被选修过。|学生不可能学完大学所开设的所有课程， 因此必须在入学时选定自己要学的课程。每个 学生可选课程的总数是给定的。现在请你找出 一种选课方案，使得你

10、能得到学分最多，并且 必须满足先修课优先的原则。假定课程之间不 存在时间上的冲突。树状动规| 输入输入文件的第一行包括两个正整数M 、N（中间用一个空格隔开）其中M表示待选课 程总数（1M1000)，N表示学生可以选的课 程总数（1NM)。以下M行每行代表一门课，课号依次 为1，2M。每行有两个数（用一个空格隔开 ），第一个数为这门课的先修课的课号（若不 存在先修课则该项为0），第二个数为这门课的 学分。学分是不超过10的正整数。|输出输出文件第一行只有一个数，即实际 所选课程的学分总数。以下N行每行有一个数， 表示学生所选课程的课号。树状动规7 4 2 2 0 1 0 4 2 1 7 1 7

11、 6 2 2表12157346图202157346图1样例分析样例分析树状动规|们可以选取某一个点k的条件只是它 的父节点已经被选取或者它自己为根节点； 而且我们不论如(何取k的子孙节点，都不会 影响到它父节点的选取情况，这满足无后效 性原则。于是我们猜测，是不是可以以节点 为阶段，进行动态规划呢？|我们用函数f(I,j)表示以第i个节点 为父节点，取j个子节点的最佳代价，则：|可是如此规划，其效率与搜索毫无差 别，虽然我们可以再次用动态规划来使它的 复杂度变为平方级，但显得过于麻烦。分析分析树状动规|转变为二叉树。如果 两节点a,b同为兄弟，则将b 设为a的右节点；如果节点b 是节点a的儿子，则将节点b 设为节点a的左节点。树改 造完成后如图3。|我们用函数f(I,j)表 示以第i个节点为父节点， 取j个子节点的最佳代价， 这和前一个函数表示的意义 是一致的，但方程有了很大 的改变：023 014765图3树状动规1 (x1, y1)的移动！ ”(Angel暗自想：还有这么心黑的)迷宫为 n*m的矩阵。骑士从(n, m)到(1, 1)。问：在戒 指的帮助下，骑士最少要多少步才能回到入口？在 步数最少的前提下，总共有多少种办法到达入口？ 注意，骑士不会傻到一直停留在原地不动。