HDOJ 4276 The Ghost Blows Light

题意

1. 给定一棵树, 树上节点有 value, 节点之间 travel 有 cost. 给定起始节点和最大 cost, 求解最大 value

思路

1. 寻找最短路径

　　a. 题目描述中有两句话, "There is exactly one route between any two rooms", "Each of the next N-1 lines contains three integers" 说明给出的结构是一棵树

　　b. 假如给定的时间小于起终节点间的最短路径, 那么逃跑失败. 否则, 会有多余的时间跑到其他节点拿到更多的价值

　　c. 使用多余的时间获取最大价值的方法在最短路径上的每个节点上分配合理的时间, 并在每个节点上合理的遍历

2. 以最短路径上的节点为树根进行树形 DP

　　a. 假设 i 表示最短路径上的某一个节点, j 表示剩余的时间. DP[i][j] 表示在 i 上分配 j 时间能够得到的最大价值

　　b. DP[i][j] = max(DP[son1][t1] + DP[son2][t2]+ ...). Son 表示节点 i 的孩子节点, t表示在某个孩子节点上分配的时间, 分配一定要使价值最大化

　　c. 分配的动态规划算法. DP[i][j] = max(DP[i][j], DP[sonx][j-2*costx-t]) 0 <= t <(j-2*costx) 这就以动归的思想解决了 b

3. 在最短路径上的每个节点上分配时间, 使获得的总价值最大

　　a. 通过步骤2, 获得了在任意节点 i 分配之间 j 所能获得的最大价值, 现在需要再最短路径上的节点上分配之间, 以使总价值最大

　　b. 这又是一步动态规划, 思路和 2.b 一样, 动归做法和 2.c 相同

巴特西