[华为OD]C卷运输时间 200 动态规划

题目：

M辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为N。速度快的车追上前车

后，只能以前车的速度继续行驶，求最后一车辆到达目的地花费的时间。

注意：

每辆车固定间隔1小时出发，比如第一辆车0时出发，第二辆车1时出发，依次类推.

输入描述

第一行两个数字：M、N,分别代表车辆数和到终点的距离，以空格分隔寸妾下来M行，每行1

个数字S代表每辆车的速度

1< M < 20

1 < N < 400

0 < S < 30

输出描述

最后一辆车到达目的地花费的时间

示例1：

输入：

2 11

输出：

5.5

说明：

2辆车，距离11, 0时出发的车速度快，1时出发的车，达到目的地花费5.5

题解：

由于题目说了，速度快的车追上前车，会在追上前车时候按照前车速度继续行驶，那么这个时候，这个速度快的车就会和前车同时到达终点。

那么就有两种情况，追不上前车，那么对应时间就是s/v

追上前车，那么时间和前车一致。明显可以使用动态规划。dp[i]就是第i+1辆车到达终点的时间。

第一辆车dp[0] = s/v[0];

第i辆车判断能追上，那么s/v[i] + 1< dp[i-1] ,因为第i辆车与前一辆车行驶时间差距1小时，所以有个-1,也就是前车耗时比后车多一个小时

此时dp[i] = dp[i-1]-1;

如果不能追上，那么dp[i] = s/v[i]

最后算出最后的dp[num-1]就可以了

代码：

import java.util.Scanner;

public class Speed {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] infos = sc.nextLine().split(" ");
        int carNum = Integer.valueOf(infos[0]);
        int dis = Integer.valueOf(infos[1]);
        int speeds[] = new int[carNum];
        for (int i = 0; i < carNum; i++) {
            speeds[i] = sc.nextInt();
        }

        double dp[] = new double[carNum];
        dp[0] = (double) dis / speeds[0];

        for (int i = 1; i < carNum; i++) {
            double time = (double) dis / speeds[i];
            if (time+i < dp[i-1]+i-1) {
                dp[i] = dp[i - 1] - 1;
            } else {
                dp[i] = time;
            }
        }
        System.out.println(dp[carNum - 1]);
    }
}

验证：