[JLOI2009]F1一级方程式大赛

……NOIp提高组难度,hhh

首先这是一道DP……这很显然。。

注意到每次加油一定是加刚好够跑整数圈的油……要不浪费时间。

然后方便起见,我们预处理跑 1 \sim n 圈的耗油和耗时,因为这和你当前在跑哪一圈是无关的。

设为了跑第 i 圈,需要用油 q_i ,每圈空车跑油 s   , 每多一升油多跑油 a , 初中数学解方程可以得到:

q_i = (q_{i-1} + q_i) \cdot a + s

q_i = \frac{s + q_{i-1} \cdot a }{1-a}

时间比较好算……就不说了。

预处理完了,我们开始dp。

设dp[i][j]表示:在第 i 圈起点,准备不加油一口气地跑 j 圈的最小时间。

转移就是(need是跑 i 圈的油量,tim是时间,incost是进加油站,gcost是加油):

然后记录一下转移的前驱,最后输出就行了。

O(n^3)

 

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据