本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-01 13:13:40

设 $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$ 的值，随后计算方程即可。