P9037 题解

· · 题解

由于绝对位置是难以维护的，所以考虑使用相对位置进行 dp。即可以看作车道上的车不动，车道在以一定的速度移动，这样我们使用车道上的位置便可以表示当前车的位置。如果再确定了时间，那么便可以唯一确定当前车在其它车道上同一位置的相对位置是什么。虽然我们可以在实数时刻和位置切换车道，但容易发现一次切换车道要么是从一个整数位置换过去，要么是换到一个整数位置。因此可以对每个整数位置，记录走到它所需的最小时刻。

但这样转移是比较麻烦的，因为我们可以在一个位置等待一些时刻，再换到别的车道。但由于我们只记录了最小时刻，所以这样的转移只能暴力去做，复杂度会变成 O(L^2)，所以我们需要分析一下整个过程有没有什么更好的性质。注意到我们可以尽可能地呆在中间车道，因为这个车道向两边变道不会受到其它车道的阻碍。我们只在需要超车的时候选择左边或右边的车道从哪里冲过去。这样看起来不是很符合直觉，因为中间车道上车的速度并不是最快的，但我们在不超车的情况下速度永远都是 v_0，所以这种情况在哪个车道并不重要。而如果在某一时刻我们车的正前方在中间车道有一辆车挡住了，即是我们现在在两侧的车道，依然会被中间车道挡在前面的车堵住而无法变道，但我们此时立即从中间车道变入某个两侧的道，便可以得到与一开始就在那个车道上一样的效果。综上所述，对于任意一个最优的方案，我们对其进行修改使得只要能在中间车道上开就一直在上面，这仍然是一组最优解。

有了这个性质之后我们便只需要对中间车道的每个整数位置进行 dp，因为既然我们尽可能要保持在中间车道，我们一定是在受到阻碍的时候才会变道，并在能够变回来的时候立即回来。注意这里有可能是在非整数位置时必须并入另外两个车道中的某个，但显然可以将这个变道的位置变为其相邻的一个整数而不改变结果。所以每次进入和出去都是在整数位置发生的事件。

记 f_i 表示从出发开始走到中间车道的位置 i 所需的最小时间，则如果 i+1 位置没有车，可以之间转移到 f_{i+1}。除此之外我们需要考虑变道以跨过 i 的下一段障碍，记 j 为 i 的下一段障碍之后的第一个可以走的位置。

如果我们从第一车道超车，那么一定是先以 v_2 的速度在中间车道跟车，在能变道的时候立即走到第一车道并速度加满（可能会被第一车道前面的车挡住，此时速度只能是 v_1），直到走到 j 为止。首先计算出当前位置在第一车道上的相对位置，并求出它前面第一个自由的位置，表示进入第一车道时所在的位置。然后可能会被障碍挡住，如果直接计算挡住的时间等等会比较麻烦，事实上有一种更便捷的方式。可以求出这个位置下一个障碍是什么，则我们不会比这个障碍更先到达 j 位置，所以这个障碍到达 j 的时刻就是我们到达 j 时刻的一个下界。另一方面，如果没有被障碍挡住，则我们会以 v_0 的速度冲到 j，所以这又是另一个下界。将这两个下界取 \max 即是我们需要求出的最小的时刻。特别地，如果不能立即走到第一车道而是需要等待，那么其实等待的时间不需要被考虑进去。此时无论我们在中间车道上怎么移动，都需要等到上一个障碍走过之后变道过去立即向前，所以此时上面所算出的障碍到达 j 的时刻仍然是一个正确的下界。

如果我们从第三车道超车，由于这个车道的速度更慢，所以我们不能在超车的过程中被第三车道的车挡住，否则就永远无法完成超车了。因此我们需要在第二车道上等待，直到第三车道出现了一个足够长的间隔能够让我们完成超车。这个所需要的间隔长度可以直接算出，因此我们相当于已知一个数组 v，对于一对 (l,x)，需要求出一个最小的 i\ge l，使得 v_i\ge x。可以通过二分和 ST 表解决。特别地，有可能现在这个位置是一个实数，且这个位置向后的间隔已经足够长，此时可以直接变道并计算答案。除此之外一定是在某一段障碍结束时变过去，所以一定是一个整数位置，使用前面的 ST 表维护即可。

这样就完成了所有的转移。最后计算答案时首先需要超过中间车道的所有障碍，除此之外在中间车道需要全速行驶超过其它两个车道的障碍，对每个车道的时间取最大值即可，复杂度 O(L\log L)。

代码