HBC223564[NOIP2000]乘积最大,动态规划,NOIP复赛Damsindistress题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

The network of dams and the war camp form a rooted tree, where the war camp is the root and the parent of a dam is the location immediately downstream of the dam. See Figure D.1 for an example. Figure D.1: Illustration of Sample Input 1. In this case Freyr only has to make 2 units of rain at the left-most dam in order to make it break and send 50 units of water downstream, which then ultimately results in 100 units of rain reaching the war camp, well exceeding the 75 units ofwater needed to flood the camp.

Freyr, the god of prosperity, rain and the harvest, is having a lot of trouble these days. The giants are once again trying to invade Midgard, and have built a war camp at the bottom of the many valleys leading to Midgard. Now Freyr needs to wash that camp away, so a great victory feast can be held. Being at the bottom of the valley, any rain in the region can make its way through rivers and streams to the bottom of the valley and contribute to the glorious flooding of the giants. However, beavers and industrious humans have built dams throughout the river system, and these act as buffers that can hold some amount of water. But, on the flip side, once a dam is filled up to its capacity, it will break and all of the water stored there (as well as any further water added) will be released downstream. Freyr, being the god of rain, knows exactly how much water is needed to wash the war camp away, and for each dam knows its exact capacity and how much water is currently stored there. Freyr, also being the god of prosperity and harvest, has better things to do than making it rain everywhere all day, so Freyr decides to only make it rain at a single place (either a dam, or the war camp), and to make it rain as little as possible in that place. What is the minimum amount of rain that Freyr needs to make to wash away the giants war camp, provided he carefully chooses the best location for the rain? The network of dams and the war camp form a rooted tree, where the war camp is the root and the parent of a dam is the location (either another dam, or the war camp)  immediately downstream of the dam. See Figure D.1 for an example. Figure D.1: Illustration of Sample Input 1. In this case Freyr only has to make 2 units of rain at the left-most dam in order to make it break and send 50 units of water downstream, which then ultimately results in 100 units of rain reaching the war camp, well exceeding the 75 units ofwater needed to flood the camp.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC223564[NOIP2000]乘积最大 动态规划 NOIP复赛Damsindistress题解