P4677 山区建小学 分析

· · 个人记录

设 f(i, j) 表示可以建 j 个小学时，给前 i 个村庄建小学的最短距离和，那么状态转移方程：

f(i, j) = \begin{cases} 0 & j > i \\ \min\limits_{k = j - 1}^i{f(k, j - 1) + \sigma_{k + 1, i}} & \text{otherwise} \end{cases}

这也就是说，给前 i 个村庄建 j 个小学的最小花费，就是从 j - 1 到 i 中选一个 k 作为分割点，在前 k 个村庄里建 j - 1 个小学，然后在 k + 1 到 i 个村庄里建一个小学。

这里面，\sigma_{i, j} 表示在 i 到 j 个村庄中建一个小学的最短距离和，它是一个定值。

那么 \sigma 怎么求呢？在 [i, j] 中，最短距离和一定是在中点处，因为每个村庄的坐标是递增的。我们可以证明，在中点处左移或者右移动，均会使最终的值更大。故中点一定最优。

所以我们就可以求出 \sigma 的值，随后计算方程即可。