题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单 位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格 Pi（i=1，2，…，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入输出格式
输入格式：第一行，D1，C，D2，P，N。
接下来有N行。
第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。
输出格式：所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入输出样例
说明
N≤6N\le 6N≤6,其余数字≤500\le 500≤500
考虑在当前加油站i，剩余油为t
下一个比i便宜的是j
如果剩余油直接到j，那么不加油直接到j
如果不够，加到正好到j
如果加满都不够，那么加满
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 double D1,C,D2,P,t,d[502],p[502],ans;
7 int n;
8 int main()
9 {int i,j,Min,l;
10 cin>>D1>>C>>D2>>P>>n;
11 for (i=1;i<=n;i++)
12 {
13 scanf("%lf%lf",&d[i],&p[i]);
14 }
15 d[n+1]=D1;
16 p[0]=P;
17 t=0;
18 for (i=0;i<=n;i++)
19 {
20 double x=d[i+1]-d[i];
21 if (x>C*D2)
22 {
23 cout<<"No Solution";
24 return 0;
25 }
26 for (j=i+1;j<=n;j++)
27 if (p[j]<p[i]) break;
28 //cout<<j<<endl;
29 if (t*D2>=(d[j]-d[i]))
30 {
31 t-=(d[j]-d[i])/D2;
32 i=j-1;
33 }
34 else
35 if (C*D2>=(d[j]-d[i]))
36 {
37 ans+=(d[j]-d[i]-t*D2)/D2*p[i];
38 i=j-1;
39 t=0;
40 }
41 else
42 {
43 ans+=(C-t)*p[i];
44 t=C-(d[i+1]-d[i])/D2;
45 }
46 }
47 printf("%.2lf\n",ans);
48 }