最后一车辆到达目的地花费的时间，动态规划解题思路

题目描述

辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为 N 。

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

注意：

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

解题思路：动态规划

“速度快的车追上前车后，只能以前车的速度继续行驶”

做题的时候容易被这个题设误导，把问题想复杂，会思考最后一辆车能否在到达终点前追上前车，追上前车的时间，以及共同行驶的时间，进而思考前一辆车是否会被更前一辆车影响，提前减速，导致最后一辆车提前追上前一辆车，影响最后一辆车到达时间，不停的向前递推，不停的判定，导致问题无法解决。

其实，如果已知前车到达目的地花费的时间dp(0)，那么只需要判断后车能否维持初始速度在 dp(0)-1 的时间内到达终点，如果能到达，那么后车必然在终点之前追上了前车，然后与前车共同行驶到终点,不需要考虑后车何时追上前车以及后车追上前车的时间点，此时后车到达终点的时间为 dp(0)-1 ，如果不能在 dp(0)-1 的时间内到达终点，说明在终点前没有追上前车，此时后车到达终点的时间为 s/v1。因此，每一辆车的到达时间只受前一辆车的到达时间影响，满足无后效性要求，适用动态规划求解，且动态转移方程为dp(i)=max{dp(i-1)-1 , s/v(i)} ,初始状态dp(0)=s/v(0)