什么是树型动态规划.pdfVIP

什么是树型动态规划 u 顾名思义，树型动态规划就是在“树”的数据结构上的 动态规划，平时作的动态规划都是线性的或者是建立在 图上的，线性的动态规划有二种方向既向前和向后，相 应的线性的动态规划有二种方法既顺推与逆推，而树型 动态规划是建立在树上的，所以也相应的有二个方向： u 根—叶：不过这种动态规划在实际的问题 中运用的不多，也没有比较明显的例题， 所以不在今天讨论的范围之内。 u 叶－根：既根的子节点传递有用的信息给 根，完后根得出最优解的过程。这类的习 题比较的多，下面就介绍一些这类题目和 它们的一般解法。 例题一：HDU 2412 PARTY AT HALI-BULA u 题目大意： u n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的 唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2 个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且 求出获得最大人数的选人方案是否唯一。 u 这是一个经典的树型动态规划。 u 状态？ u 转移？ 1.2 Party at Hali-Bula u 简单的染色统计是不正确的 1.3 Party at Hali-Bula u 人之间的关系形成树型结构 u DP, 用dp[i][0]表示不选择i点时，i点及其子树能选出的 最多人数，dp[i][1]表示选择i点时，i点及其子树的最多 人数。 1.4 Party at Hali-Bula u 状态转移方程: u 对于叶子节点dp[k][0] = 0, dp[k][1] = 1 u 对于非叶子节点i, u dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i 的儿子) u dp[i][1] = 1 + ∑dp[j][0] (j是i 的儿子) u 最多人数即为max(dp[0][0], dp[0][1]) u 如何判断最优解是否唯一? 1.5 Party at Hali-Bula u 新加一个状态dup[i][j]，表示相应的dp[i][j]是否是唯一 方案。 u 对于叶子结点, dup[k][0] = dup[k][1] = 1. u 对于非叶子结点, u 对于i 的任一儿子j ，若(dp[j][0] dp[j][1] 且dup[j][0] == 0) 或 (dp[j][0] dp[j][1] 且dup[j][1] == 0) 或 (dp[j][0] == dp[j][1])，则dup[i][0] = 0 u 对于i 的任一儿子j有dup[j][0] = 0, 则dup[i][1] = 0 例题二：STRATEGIC GAME u 题目大意： u 一城堡的所有的道路形成一个n个节点的树，如果在一 个节点上放上一个士兵，那么和这个节点相连的边就会 被看守住，问把所有边看守住最少需要放多少士兵。 u 典型的树型动态规划 u 状态？ u 转移？ 2.2 Strategic game u dproot[ i ]表示以i为根的子树，在i上放置一个士兵，看 守住整个子树需要多少士兵。 u all[ i ]表示看守住整个以i为根的子树需要多少士兵。 2.3 Strategic game u 状态转移方程： 叶子节点：dproot[k] =1；all[k] = 0； 非叶子节点： dproot[i] = 1 + ∑all[j](j是i的儿子)； all[i] = min( dproot[i], ∑dproot[j](j是i的儿子) ); 例题三 CF 337D Book of Evil u 题意：在一颗树上，给m个点，求到所有m个点距离不