题目名称	612. 摩托车游戏
输入输出	`carz.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2011-11-09加入
开放分组	全部用户
提交状态
分类标签	动态规划背包问题
	分享题解

通过：99，提交：182，通过率：54.4%
521	100	0.000 s	0.00 MiB	C++
dateri	100	0.000 s	0.00 MiB	C++
BaDBoY	100	0.000 s	0.00 MiB	C++
Tanya	100	0.000 s	0.00 MiB	C++
Regnig Etalsnart	100	0.000 s	0.03 MiB	C++
open the window	100	0.002 s	0.32 MiB	C++
饺子	100	0.003 s	0.31 MiB	C++
饺子	100	0.003 s	0.31 MiB	C++
饺子	100	0.003 s	0.32 MiB	C++
实力演员阵容	100	0.003 s	0.36 MiB	C++

本题关联比赛
20111109
20111109
20151026
20151026

关于摩托车游戏的近10条评论(全部评论)
可以集体乘上 7560[b]，用 int 可解，50行过。 7560是 75 90 80 60 70的公倍数；以十公里为一个判断点，分别求出初始油量的5个状态的十公里耗时，这时全部的数都是整数；下面是我的方法：手推30min的DP [b] 在时间最优时，易推出每次加油时油箱均为空由速度V为常数将距离 S 转化为时间 s= S /10 假设现在已知方案时间最少；则对于最后一次在 Q 时间的加油有： · Q~S耗时已知问题转换为求 0~ ( Q )的最优解先用前缀和优化，然后用递推解决，反正我不会用浮点型； konnyaku 2017-10-23 20:57 9楼
完全背包不需要黄桃 2017-10-16 21:50 8楼
暴力DP。。。小字、小瓶子 2017-10-16 21:09 7楼
[size=40]出门左转有几率获得双倍经验[/size] +1s 2017-09-09 09:12 6楼
哈哈 Fisher. 2017-07-04 09:06 5楼
另外2013暴力摩托和此题一样 open the window 2016-09-29 09:45 4楼
事实上这是一道完全背包…… open the window 2016-09-29 09:43 3楼
看错题。。原来不会因为中途油量减少而加速的啊。。不符合客观事实！！ HouJikan 2014-09-28 10:54 2楼
线性动规， f10[i]表示到10*i为止花费的最小费用。读题会发现其实赛车只会走10的整数倍的距离。对此，有些量需要缩小十倍，以保证空间复杂度不至于过高。 Truth.Cirno 2011-11-09 13:09 1楼

612. 摩托车游戏

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

[问题描述]

晚会上大家在玩一款“暴力摩托”的游戏，它拥有非常逼真的画面和音响效果，如疾驰而过的汽车呼啸声，摩托车的引擎声和转弯时轮胎与地面摩擦而产生的声音。而且它在游戏中加入了对抗成份，比赛中你可以使用拳、脚去干扰对方，使其落后于你，是不是很卑鄙啊 ? 游戏中千万不能手下留情，因为对手会主动攻击你。如果遇到开摩托车的警察，虽然也可以对他踢上一脚，但可得小心点呀，万一被他们捉住了，那就 GAME OVER 啦!

当然了，车子总是要加油的咯，已知赛道长 S公里（S≤10000整数，且为10的倍数），赛车的油耗Q=1，即 1公里路耗 1个单位的油。Q不变，赛车的油箱为无穷大，同时在沿途的任何地方都可以加油。约定，每次加油的数量为整数，且为 10的倍数，赛车的速度与赛车加油后的总油量有关。其关系如下表列出：

总油量	车速（公里 / 小时）
≤10	100
（ 10 ， 20 ]	90
（ 20 ， 30 ]	80
（ 30 ， 40 ]	75
（ 40 ， + ∞ ）	70

同时，汽车每加油一次需要耗费 T分钟（T<=100不论加油多少，开始时的加油不计时间）

当 S，T给出之后，选择一个最优的加油方案。使汽车以最少时间跑完全程。

例如：当 S=40，T=6（分钟），加油的方案有许多种，列出一些：

1）起点加油40，用时40/75≈0.53小时

2）起点加油20，中途加20，用时20/90+20/90+6/60（化为小时）≈ 0.54 小时

[输入文件]

一行，为两个整数 S、T。

[输出文件]

输出一行，为最少用时（保留二位小数）

[输入样例]

40 6

[输出样例]

0.53