NOI2019同步赛体验&感想
(>﹏<) 今年暴力分比去年足诶！！（暴力选手真心话
来补题解啦，由于咕咕了很久所以已经忘记题目顺序啦
$回家路线$
同步赛时写了以边为点的 $O(m^2)$ 最短路。听说数据很水，emm
$p < q$，显然不会构成环，dp 就行了
正解是斜率优化 dp，$f[i]$ 表示走了第 $i$ 条边的最小烦躁值。$f[i] = min(f[j] + calc(p_i - q_j)(y_j = x_i, q_j \leq p_i))$
对于最优解 $j$, $f[j] + Ap_j^2 - Bq_j = 2Ap_iq_j + f[i] - Ap_i^2 - Bp_i - C$
其中 $y = f[j] + Ap_j^2 - Bq_j$,
$k = 2Ap_i$,
$x = q_j$,
$b = f_i - Ap_i^2 - Bp_i - C$
要 $f_i$ 小就是要截距小，因此维护一个下凸包
以时间为阶段，维护 $t$ 时间内的凸包集合，即集合内决策点满足 $q_i \leq t$. 桶排，将决策点 $j$ 在时刻 $q_j$ 加入凸包 $y_j$ 中。每个凸包满足 $q$ 递增。
RE 调半天，发现数组没开足。。。