题解 P5468 【[NOI2019]回家路线】

· · 题解

这题就是这道题的加强版。

首先，我们不考虑位置的限制，只考虑过程。

我们可以设 dp[i] 表示在时刻 i 时的最小烦躁值减去 q_{s_k} ，则有:

对于一条路径 (p_r,q_r)(我们此时不考虑 x 和 y ):

dp[q_r]=\min_{j\le p_r}dp[j]+A(p_r-j)^2+B(p_r-j)+C

明显可以利用斜率优化加速转移。

但是问题在于路径是一个持续性的过程，即 p_i 和 q_i 之间可能相距很远。不过我们完全可以将 p_i 和 q_i 拆成 一次询问 和 一次尾部插入 两个事件，这样事件就可以通过排序变成时间单调递增的了。

接下来考虑 x 和 y ，也就是起点和终点。不过这可以用上面一样的方法处理，也就是将起点和终点拆成两个操作。我们依然维护单调队列，但是因为每个事件对应的地点有区别，因此我们对每个点开一个 vector ，分别维护即可。

记得在 1 号点预先放一个 0 时刻 0 代价的点作为起点。答案可以在路径终点是 n 的时候直接统计，n 号点就没必要再开 vector 了。

时间复杂度瓶颈在排序上。因为数据范围特别小，因此可以直接采用统排。时间复杂度 O(M+T)，其中 T 是时间范围的最大值。

代码就不贴了。