题目名称 89. 驾车旅行
输入输出 tour.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2008-09-08加入
开放分组 全部用户
提交状态
分类标签
搜索法 动态规划
分享题解
通过:62, 提交:164, 通过率:37.8%
Gravatarelysian 100 0.003 s 0.00 MiB Pascal
GravatarZhouZn1 100 0.003 s 0.11 MiB Pascal
Gravatar王瑞祥K 100 0.003 s 0.11 MiB Pascal
Gravatarlizhe 100 0.003 s 0.12 MiB Pascal
Gravatarlizhe 100 0.003 s 0.12 MiB Pascal
Gravatar11111111 100 0.003 s 0.26 MiB C++
GravatarCzb。 100 0.003 s 0.26 MiB C++
GravatarBFZD 100 0.003 s 0.31 MiB C++
Gravatarforever 100 0.003 s 0.32 MiB C++
Gravatar · 100 0.003 s 0.54 MiB C++
本题关联比赛
NOIP_2
NOIP_2
20200605
关于 驾车旅行 的近10条评论(全部评论)
回溯。。。
分程序里一开始把y设成int,全错。。。
改成float。。。全过。。。
退役倒计时。。。
GravatarZwoi_只会打表抄代码的蒟蒻
2016-11-14 18:24 3楼
DFS全過!
GravatarMakazeu
2011-11-01 10:29 2楼
BFS过全,注意第一个限制,需要仔细理解:
除非汽车无法用油箱里的汽油达到下一个加油站或目的地,在油箱里还有不少于最大容量一半的汽油时,驾驶员从不在加油站停下来。
后半句不解释。
前半句说明,也有在油量大于最大容量一半时加油的情况。
GravatarTruth.Cirno
2011-10-30 13:00 1楼

89. 驾车旅行

★★   输入文件:tour.in   输出文件:tour.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

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

  (1)除非汽车无法用油箱里的汽油达到下一个加油站或目的地,在油箱里还有不少于最大容量一半的汽油时,驾驶员从不在加油站停下来;

  (2)在每一个停下的加油站总是将油箱加满,

  (3)在加油站加油的同时,买快餐等吃的东西花去20元。

  (4)从起始城市出发时油箱总是满的。

  (5)最终结果精确到0.1元(四舍五入)。

  (6)驾车者都知道自己的汽车每升汽油能够行驶的里程数。

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

【输入格式】

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

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

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

数据项中的每个数据都是正确的,不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离.

【输出格式】

就一个数据,是精确到0.1元的最小的加油和吃饭费用。

【输入样例】

600
40 8.5 128 3
200  3.52
350 3.45
500 3.65

【输出样例】

379.6