P1016 旅行家的预算

admin

题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离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”。

输入输出样例
输入样例#1：
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出样例#1：
26.95
说明
N≤6,其余数字≤500

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. double d[1000]={0},p[1000],dm,s,c,money=0,oil=0;
    
14. int n;
    
15. void aha(int mu,int no,int l)
    
16. {
    
17.     if(no==n+1)
    
18.     {
    
19.         printf("%.2lf",money);
    
20.         return ;
    
21.     }
    
22.     if(no<mu)
    
23.     {
    
24.         int e=l;
    
25.         if(p[no]<p[l])
    
26.             money-=oil*(p[l]-p[no]),e=no;
    
27.         oil-=(d[no+1]-d[no])/dm;
    
28.         aha(mu,no+1,e);
    
29.         return ;
    
30.     }
    
31.     else if(no==mu)
    
32.     {
    
33.         int k=no+1;
    
34.         while(p[k]>p[no])
    
35.             k++;
    
36.         if(d[k]-d[no]<=dm*c)//跑得到
    
37.         {
    
38.             if(oil<(d[k]-d[no])/dm)
    
39.             {
    
40.                 money+=((d[k]-d[no])/dm-oil)*p[no];
    
41.                 oil=(d[k]-d[no])/dm;
    
42.             }
    
43.             aha(k,no,no);
    
44.             return ;
    
45.         }
    
46.         else//跑不到
    
47.         {
    
48.             int t=no+1;
    
49.             while(d[t]-d[no]<=dm*c)//跑的越远越好
    
50.                 t++;
    
51.             money+=(c-oil)*p[no],oil=c;
    
52.             aha(t-1,no,no);
    
53.             return ;
    
54.         }
    
55.     }
    
56. }
    
57. int main()
    
58. {
    
59.     scanf("%lf%lf%lf%lf%d",&s,&c,&dm,&p[0],&n);
    
60.     for(int i=1;i<=n;++i)
    
61.     {
    
62.         scanf("%lf%lf",&d[i],&p[i]);
    
63.         if(d[i]-d[i-1]>dm*c)
    
64.         {
    
65.             printf("No Solution");
    
66.             return 0;
    
67.         }
    
68.     }
    
69.     d[n+1]=s;
    
70.     if(d[n+1]-d[n]>dm*c)
    
71.     {
    
72.         printf("No Solution");
    
73.         return 0;
    
74.     }
    
75.     aha(0,0,0);
    
76.     return 0;
    
77. }
    

复制代码