问题是：
我们想要从一个地方到另一个地方乘坐卡车远离它的D（D <= 1,000,000,000）单位 . 卡车可以容纳G（G <1,000,000）单位的燃料，并且在1个单位距离内消耗1单位燃料 . 沿途有N（N <= 50,000）个加油站 . 每个站点距起点都是X_i单位，每单位燃料的价格是Y_i（Y_i <= 1,000,000） . 我们用B单位燃料开始旅程 . 到达目的地的最低费用是多少？
（Actual problem statement来自USACO过去的比赛）
我的算法：
设F [i] =到达加油站i和第N个加油站所需的最低成本是目的地 .
假设k是我们在到达i之前填充油箱的最后一站， F[i] = F[k] + Y_k * (X_i-X_k) . 我们为所有k <i尝试这个，这样 X_i-X_k < D 并取最小值 .
F [N 1]将是最终答案 .
这个算法的问题：
1.将需要O（N2）时间，该时间不会在2秒的时间内运行 .
2.它考虑的情况是我们到达一个已经有m单位燃料的燃料站k，我们只填充X_i-X_k-m单位的燃料到达i .
我该如何克服这些问题？
1 回答
该竞赛针对所有9个问题发布了官方解决方案：
http://www.usaco.org/index.php?page=open13problems