#HX2682. 搜索回溯问题综合测评题七:驾车旅行

提交2 通过1
通过率50%
时间限制1000ms
内存限制128MiB
    ID: 12818 传统题 1000ms 128MiB 尝试: 2 已通过: 1 难度: 普及+/提高- 上传者: 标签>C++c++编程题浩轩OJ迁移6级2025年寒假六级班题库

题目描述

题目描述

如今许多普通百姓家有了私家车,一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题,在出发之前,驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表,列表中包括了所有加油站的位置及其每升的油价(如 3.25元/L)。驾车者一般都有以下的习惯:

每当驾驶员到达一个加油站时:

1.如果油箱里的汽油已经不够达到下一个加油站或目的地,驾驶员必须在当前加油站停下来加油。

2.如果汽油足够到达下一个加油站,但是油箱的汽油小于最大容量一半时,驾驶员可以选择加油或者不加油。

3.如果汽油足够到达下一个加油站,且油箱的汽油大于等于最大容量一半时,驾驶员一定不会加油。

每次加油一定会将油箱加满。驾驶员在等待加油的同时要花20元买吃的。

驾驶员在出发时花费c元将油箱加满。现在要你帮忙做的就是编写一个程序,计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。

输入格式

第一行是一个实数L,是从出发地到目的地的距离(单位:公里)。

第二行是三个实数v,m,c和一个整数n,其中第一个实数v是汽车油箱的最大容量(单位:升);第二个实数m是汽车每升油能行驶的公里数;第三个实数是c汽车在出发地加满油箱时花掉的费用(单位:元);一个整数n是 1 到 50 间的数,表示从出发地到目的地线路上加油站的数目。

接下来 n 行都是两个实数di,pi,第一个数表示从出发地到某一个加油站的距离(单位:公里);第二个实数表示该加油站汽油的价格(单位:元)。

数据保证驾驶员一定可以到达目的地。一条线路上的加油站根据其到出发地的距离递增排列,并且都不会大于从出发地到目的地的距离。

输出格式

输出一个实数,最小的加油和吃饭费用,输出时四舍五入到0.1。

输入样例 #1

600
40 8.5 128 3
200 3.52
350 3.45
500 365

输出样例 #1

13133.2

输入样例 #2

215.003
21.790 10.963 195.926 1
107.502 18.224

输出样例 #2

195.9

输入样例 #3

957.685
79.677 8.903 60.454 2
319.228 4.237
638.456 8.103

输出样例 #3

661.5

数据范围与约定

1≤n≤50;其余数值在double范围内;站点按距离递增且保证可以到达。