HBC24623能量水晶,背包问题,动态规划,思维Tree Decoration题解

淫家是湿人 算法基础篇 55 0
不断提升技能,才能在职场中立于不败之地!全网最全C++题库,助您成为编程领域的佼佼者。
Farmer John is decorating his Spring Equinox Tree . It can be modeled as a rooted mathematical tree with N (1

Farmer John is decorating his Spring Equinox Tree (like a Christmas tree but popular about three months later). It can be modeled as a rooted mathematical tree with N (1 <= N <= 100,000) elements, labeled 1...N, with element 1 as the root of the tree. Each tree element e > 1 has a parent, P_e P e ​ (1 <= P_e P e ​ <= N). Element 1 has no parent (denoted '-1' in the input), of course, because it is the root of the tree. Each element i has a corresponding subtree (potentially of size 1) rooted there. FJ would like to make sure that the subtree corresponding to element i has a total of at least C_i C i ​ (0 <= C_i C i ​ <= 10,000,000) ornaments scattered among its members. He would also like to minimize the total amount of time it takes him to place all the ornaments (it takes time K* T_i T i ​ to place K ornaments at element i (1 <= T_i T i ​ <= 100)). Help FJ determine the minimum amount of time it takes to place ornaments that satisfy the constraints. Note that this answer might not fit into a 32-bit integer, but it will fit into a signed 64-bit integer. For example, consider the tree below where nodes located higher on the display are parents of connected lower nodes (1 is the root): 1 | 2 | 5 / 4 3 Suppose that FJ has the following subtree constraints: Minimum ornaments the subtree requires | Time to install an ornament Subtree | | root | C_i | T_i --------+--------+------- 1 | 9 | 3 2 | 2 | 2 3 | 3 | 2 4 | 1 | 4 5 | 3 | 3 Then FJ can place all the ornaments as shown below, for a total cost of 20: 1 [0/9(0)] legend: element# [ornaments here/ | total ornaments in subtree(node install time)] 2 [3/9(6)] | 5 [0/6(0)] / [1/1(4)] 4 3 [5/5(10)]

HBC24623能量水晶,背包问题,动态规划,思维Tree Decoration题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: HBC24623能量水晶 背包问题 动态规划 思维Tree Decoration题解