#2294. 【POJ Challenge】爬山II

lqp18_31给了1tthinking一个很难的问题。这个问题由NWERC 2011某道题改编而来。下面是这个问题:

你在家乡的一个山坡上开车回家。你想尽可能快的回家，但是你的油箱里没有太多油了。回家的路是由一些上坡和下坡组成的。每个坡有不同的斜率和长度。如何可以在油量限制的前提下，最快回家呢？

我们把油量的消耗简化为一个很简单的模型。每小时油量消耗会随着速度 v 线性递增。但是，油量还和坡的斜率 s 有关。 举个例子，当走下坡路的时候，你可以以10千米每小时的速度行走而不花费任何的油。然后如果你走上坡路，你就需要耗油了。 更加详细的说, 你的汽车每小时耗油是 c。那么

c = max(0, αv + βs),

其中 α 和 β 是两个常数， v 是你的速度 km/h, s 是斜率。 加速和减速不花费油，且可以瞬间完成。

你的车有一个安全速度，你永远也不能超越这个速度vmax 且在一个斜坡上，你必须以同样的速度行驶，不能变速.