#P1140. 第4题-倒水魔法

第4题-倒水魔法

题目内容

小美是一个年轻的魔法学徒,他一直在努力学习各种魔法技能。他听说倒水魔法是一种非常强大的魔法,但也是一种非常难掌握的魔法。他早早地来到了魔法训练室,希望能够掌握这种魔法。

魔法训练室里有 nn 个神奇的杯子,有着不同的大,假设第 ii 个杯子已满,向其倒水,多余的水会正正好好流向第 i+1i+1 个杯子(如果 i=ni=n 时没有下一个杯子,不会有杯子接住此时多余的水而溢出到魔法训练室的水池)。

这些杯子有着初始固定的水量,每次练习后杯子里的水都会还原到最初状态。每次练习时,魔法黑板会告诉小美需要将哪一人杯子倒满水。因为每个杯子的材质和形状有所不同所以对其释放倒水魔法需要消耗的魔法值不同。小美想尽可能多练习,所以需要最小化每次消耗的魔法值的总量。