mengbierr

一个蒟蒻的博客

1月06

Codeforces1091F. New Year and the Mallard Expedition

题目大意

有一段分为n段的路,有草地,水和岩浆。可以在草地上走,水里游泳,任何地形上飞,走1单位消耗5单位时间,获得1点能量;游泳消耗3单位时间,获得1点能量;飞消耗1单位时间,消耗1点能量,求走完这段路的最短时间。

题解

先假设在所有草地上走,在水中游泳,在岩浆上飞。
如果某一时刻需要飞而能量不足,可以在前面的某处反复移动获得能量,如果有水优先游泳。
如果最后能量过多,就需要将前面游泳或走的一段路变成飞,但必须保证不能在某个位置能量为负。
我们应该尽可能多的将走路转化成飞,从头开始维护这个值,显然不能超过草地的长度,因为不能出现能量为负的位置,还需要用当前能量/2更新这个值。

发表评论

电子邮件地址不会被公开。 必填项已用*标注