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

Great_Influence

2019-07-16 14:57:18

Solution

这题就是[这道题](https://loj.ac/problem/6520)的加强版。 首先,我们不考虑位置的限制,只考虑过程。 我们可以设 $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$ 是时间范围的最大值。 代码就不贴了。