#P1414. 好了你已经知道最优解了请实操吧
好了你已经知道最优解了请实操吧
好了你已经知道最优解了请实操吧
小王最近迷上了玩双人成行,但是没想到擅长体育的她手部协调能力却异常的差,连手柄都用不好,但是小王的编程能力和算法功底却是一等一的好,但是她又很懒于是把思路给了你,想必聪明的你一定有办法根据她的描述解决这个问题:
在你面前有很多个条状平台,你需要通过各种操作计算出从第一个平台的前段到达最后一个平台末端的最短时间
已知有这样几个操作:疾跑,跳跃,冲刺
疾跑:在平台上,角色可以以稳定速度向前奔跑
跳跃:由于小王用的是轻薄本,游戏只有一帧,所以人物的跳跃近似的卡成了瞬移动作(真来抛物线拿头算呀)
冲刺:冲刺可以不下落的向前冲刺一段距离,然后保持原来应有的运动轨迹(你可以在空中使用冲刺)
为了简化计算,现有以下规定:
很显然,游戏里不归牛顿管,人物在冲刺过程中忽略地心引力(为了方便出题),时间会流逝但是角色不会下落,即不占用滞空时间,但是冲刺需要时间
小王的控制能力较弱,所以疾跑过程中是不能冲刺的,也就是只能在空中冲刺
跳跃和冲刺必须完成整个过程,不能说什么跳一半落下这种
每个平台间高度相同,每次跳跃或跳跃加冲刺必须满足起跳点在一个平台末端,落点在一个平台前端
接下来会给出疾跑速度,跳跃时水平速度和滞空时间,冲刺速度,及平台分布(有些关卡跳的多更有优势,有些关卡走的多更有优势,所以也许不正当的贪心会有风险)
小王用轻薄本,游戏居然达到了2帧的“电竞水平”,导致在平台上消耗的时间向下取整,如平台长9,奔跑速度为2,则耗时4秒通过
输入:
第一行四个数字分别表示:疾跑速度,跳跃时水平速度,跳跃的滞空时间,冲刺速度,冲刺时间
第二行为一个数字n,表示平台个数
第三行为2n个数字 表示每个平台的前端和末端坐标
输出:
一个数字,表示从第一个平台的前段到达最后一个平台末端的最短时间
如果无解输出-1
样例1:
输入:
4 4 1 5 1
3
1 9 13 17 26 30
输出:
7
样例1解释:
第一个平台1~9共8个单位长度 用时8/4=2秒,第一个平台与第二个差了13-9=4个单位 可用1秒的跳跃完成 第二个平台长17-13=4个单位 用时4/1=1秒,第二个平台与第三个平台直接差了26-17=9个单位 通过次跳跃加冲刺共2秒可以完成,第三个平台长30-26=4个单位 用时4/1=1秒。总计2+1+1+2+1=7秒
样例2:
输入:
8 5 1 9 1
4
1 9 14 22 23 31 36 44
输出:
6
样例2解释:
第一个平台用时1秒 然后此时面临两个抉择
1.穿过第一个平台用时1秒,进行一次跳跃到第二个平台用时1秒,穿过第二个平台用时1秒,跳跃加冲刺到第四个平台用时2秒,通过第四个平台用时1秒。总用时6秒
2.穿过第一个平台用时1秒,进行一次跳跃加冲刺到三个平台用时2秒,穿过第三个平台用时1秒,跳跃到第四个平台用时1秒,穿过第四个平台用时1秒。总计6秒
可以发现两种方案出现了不同的跳跃策略
数据范围:
都是int可以写的下的
题目出的太烂了,编题人懒得造数据了,反正n肯定小于10000
好了现在你现在知道最优解了,该你了(递过手柄)
疾跑->跳跃->冲刺。。。。。。.
。。。。。屏幕一黑。。。。。。
相关
在下列比赛中: