题解：P2803 学校选址 II

· · 题解

题目大意

共有 n 栋楼房需要选择 k 个点使得在楼里面的所有学生到学校的距离最小。

题目思路

我们先来考虑一个简化版的问题，如果每个楼房的学生数量一样多并且只能选择一个楼房使得所有小学生的上学距离最小，很容易发现一定是选择中间的点建立小学最合适。我们回到原本的问题，当前 i-1 栋楼房里的学生数量比第 i 栋到第 n 栋楼房的学生数量更多时根据前面的结论得出因该建立在第 i 栋房屋上建立学校，否则在 i-1 的位置建立学校。

我们可以得出一个二维数组 g_{i,j}，代表第 i 栋到第 j 栋楼房最优的放置学校的位置。g 数组可以通过前一段的推到求出。接下来我们定义动态规划的状态。定义 dp_{i,k} 表示在前 i 栋楼内建立 k 所学校的最短距离。当 k \le i 的情况发生说明每一栋建筑都可以建小学最短距离为 0；如果 k=1 的情况发生说明之建立一所小学根据定义可以得出：

dp_{i,k}=g_{1,i}

接下来就是普通情况，可以按照最右边的学校对楼房里的学生来分类，如果是建在 a_l 到 a_i 间，那么得出的贡献是 dp_{l-1,k-1}+g_{l,i}。最后答案根据定义可以得出应该输出 dp_{n,k}。

有了状态转移方程代码不会难写这里不给出代码，如果只是为了看代码请移步到其他题解。