P5468回家路线如何规划？
摘要：P5468 [NOI2019] 回家路线 大意 从 (1) 号点到第 (n) 号点，每个地方是一个站点，有 (k) 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？ 思路
P5468 [NOI2019] 回家路线
大意
从 \(1\) 号点到第 \(n\) 号点，每个地方是一个站点，有 \(k\) 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？
思路
我们发现如果我们按时间进行排序，处理每个站点的航线的话，我们发现这样的话，后面的站点只能从前航线时间转移过来，那么这样的话我们做 DP 是没有后效性的，我们的转移是这样的，对于一个站点，若两条航线 \(v_j = u_i\)，那么有：
\[dp[i] = \min_{j \in \text{valid}} \{ dp[j] + A(p_i - q_j)^2 + B(p_i - q_j) + C \}
\]
我们不妨把这个转移式子拆开：
\[dp[i] = dp[j] + Ap_i^2 - 2Ap_iq_j + Aq_j^2 + Bp_i - Bq_j + C
\]
再把和 \(i\) 与 \(j\) 有关的项分开：
\[dp[i] = \underbrace{(dp[j] + Aq_j^2 - Bq_j)}_{\text{跟 } j \text{ 有关}} - \underbrace{2Ap_iq_j}_{i, j \text{ 混合}} + \underbrace{(Ap_i^2 + Bp_i + C)}_{\text{跟 } i \text{ 有关}}
\]
我们发现其实是可以做斜率优化的，我们将其化为 \(y = kx + b\) 的形式：
\[\underbrace{dp[j] + Aq_j^2 - Bq_j}_{y} = \underbrace{(2Ap_i)}_{k} \cdot \underbrace{q_j}_{x} + \underbrace{(dp[i] - Ap_i^2 - Bp_i - C)}_{b}
\]
接下来维护一个下凸壳即可，由于是静态的，我们可以考虑直接用单调队列维护，但是有个很大的问题是，这些站点的东西要混起来吗？？？那怎么能知道哪个站点的能转移的点在哪呢？很简单的方式就是，我们直接维护 \(n\) 个单调队列即可。每次对于每个站点进行转移即可。