P4655 [CEOI2017] Building Bridges
2huk
·
·
题解
快进到 DP 式子：
\begin{aligned}
f(i) &= \min \{f(j) + (h_i - h_j)^2 + s_{i-1}-s_j\} \\
&= \min \{f(j) + h_i^2 + h_j^2 - 2h_ih_j + s_{i-1} - s_j\} \\
&= \min \{-2h_ih_j + f(j) + h_j^2 - s_j\} + h_i^2 + s_{i-1} \\
\end{aligned}
视 -2h_j = y，f(j) + h_j^2 - s_j = b，那么前面的 \min 等价于求当 x = h_i 时直线 y = kx+b 的最小值。李超树即可。