Problem 3676 --护卫队(convoy)

3676: 护卫队(convoy)

"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
护卫车队在一条单行的街道前排成一队,前面河上是一座单行的桥。因为街道是一条单
行道,所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通,
桥两边各站一个指挥员。护卫车队被分成几个组,每组中的车辆都能同时通过该桥。当一组
车队到达了桥的另一端,该端的指挥员就用电话通知另一端的指挥员,这样下一组车队才能
开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。
被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队
中速度最慢的车通过该桥所需的时间来表示的。要求计算出全部护卫车队通过该桥所需的最
短时间值。
输入文件第一行包含三个正整数(用空格隔开),第一个整数表示该桥所能承受的最大
载重量(用吨表示);第二个整数表示该桥的长度(用千米表示);第三个整数表示该护卫队中
车辆的总数(n<1000)。接下来的几行中,每行包含两个正整数 W 和 S(用空格隔开),W 表示
该车的重量(用吨表示),S 表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重
量和速度是按车子排队等候时的顺序给出的。
输出文件应该是一个实数,四舍五入精确到小数点后 1 位,表示整个护卫车队通过该
桥所需的最短时间(用分钟表示)。
100 5 10 
40 25 
50 20 
50 20 
70 10 
12 50 
9 70 
49 30 
38 25 
27 50 
19 70
75.0
所有数据都在 int 范围内,但是中间和输出结果可能超 int。

推荐代码 查看3676 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛