如何计算驾驶汽车以最少费用从一个城市到另一个城市的最佳路线

锣鼓P1016（旅行者预算）

问题描述

旅行者希望以最小的成本驾驶汽车从一个城市到另一个城市（假设启动时油箱是空的）。给定两个城市之间的距离 D1、汽车油箱容量 C（升）、每升汽油可行驶的距离 D2、起点 PP 处每升汽油的价格以及加油站数量沿途N（N可以为零），加油站ii到起点的距离Di，每升汽油价格Pi（i=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No”。

输入格式

第一行，D1、C、D2、P、N

接下来有N行。

第i 1行，两个数字，第i个加油站到起点的距离Di和每升汽油的价格Pi。

输出格式

所需的最低费用，四舍五入到小数点后两位。如果无法到达目的地，则输出“No”。

解决问题的思路

这个问题问得有点麻烦。本来想用滚动阵列，就像P1004一样，但是有一个问题，涉及到车内的油量。如果前面的油没有用完，会影响后面的成本。换句话说，它们不是独立的问题，而是相互关联的。

但我们可以结合实际来考虑这个问题。现实生活中，如果我们长途旅行，如果汽车油箱里的油都用完也无法到达两个加油站之间的距离，那么我们只能输出“No”，表示没有任何东西可以做到，但我们确实无法到达那里。那么即使到了那里，我们还是要考虑成本。毕竟我们省下来的钱可以用来买很多好吃的。这里我们可以知道C*D2就是我们的到达范围。如果附近有一个加油站比我们现在所在的加油站便宜，那么只要到达那个加油站就可以了，因为我们可以在剩下的路程中使用更便宜的汽油。如果碰巧，我们能到达的范围内的油价都比我们当前所在加油站的油价贵，那么我们就加油，选择那些昂贵的加油站中最便宜的加油站作为下次加油观点。我们一路前行，终于到达了目的地城市。这个时候油箱里应该已经没有汽油了，这说明我们花的钱刚刚好。

因为这些题是我自学的，所以我不知道如何实际判断正确性。但请注意，本题测试点的答案是 0，位于 0.01 位置。我在第一次输出时没有输出这个0，结果是WA。是的，还是太年轻了。

很便宜，给你看我的代码。

代码

#include #include using namespace std; double d1; double c; double d2; double p; int n; double pi[8]; double di[8]; double cost; int main() { cin >> d1 >> c >> d2 >> p >> n;