$$山区建小学$$

题目链接：$luoguP4677$

题目

政府在某山区修建了一条道路，恰好穿越总共$n$个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为$d_i$（为正整数），其中，$0<i<n$。为了提高山区的文化素质，政府又决定从$n$个村中选择$m$个村建小学。请根据给定的$n$、$m$以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

输入

第$1$行为$n$和$m$，其间用空格间隔。

第2行为$n-1$个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。

$例如：$

$103$
$246524313$

表示在$10$个村庄中建$3$所学校。第$1$个村庄与第$2$个村庄距离为$2$，第$2$个村庄与第$3$个村庄距离为$4$，第$3$个村庄与第$4$个村庄距离为$6$，$...$，第$9$个村庄到第$10$个村庄的距离为$3$。

输出

各村庄到最近学校的距离之和的最小值。

样例输入

10 2
3 1 3 1 1 1 1 1 3

样例输出

18

数据范围

$0<m<=n<500$

$0<d_i<=100$

思路

这道题是一道动态规划。

要做出这道题，最重要的一部是怎么求出$i$到$j$第之间的所有村庄都到一个学校时，所需要的距离总和的最小值。
那么在这里呢，我们就认为最中间的村庄就是可以让距离总和最小的。我们用$f[i][j]$表示，在第$i$个村庄到第$j$个村庄中只建一个学校所能获得的最小距离总和。那么我们就可以通过前缀和和我们的贪心求出$f$。

接着呢，我们就可以通过$dp$求出答案。至于怎么$dp$呢，很简单，就是这个：
$$f[i][j]=min(f[i][j],f[k][j-1]+dis[k+1][i])（j-1<=k<=i）$$
其中，$dis$表示我们之前算出来的距离，而$k$就表示分界点。
这个其实就是一个$Floyed-Warshall$算法，只是表示的方法不一样，而且因为$n$最大只有$500$，所以三重循环是可行的。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m, a[501], dis[501][501], f[501][501];

int main() {
	scanf("%d %d", &n, &m);//读入
	for (int i = 2; i <= n; i++) {
		scanf("%d", &a[i]);//读入
		a[i] += a[i - 1];//前缀和
	}
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++) {
			int school = (i + j) >> 1;//应该建的位置
			for (int k = i; k <= j; k++)
				dis[i][j] += abs(a[school] - a[k]);//求出距离
		}
	
	memset(f, 0x7f, sizeof(f));//初始化
	f[0][0] = 0;//初始化
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (j > i) {
				f[i][j] = 0;//每个地方都可以建学校
				continue;
			}
			for (int k = j - 1; k <= i; k++)
				f[i][j] = min(f[i][j], f[k][j - 1] + dis[k + 1][i]);//动态转移方程
		}
	
	printf("%d", f[n][m]);//输出
	
	return 0;
}

$Youca{n}^{\prime }tseeme.$$Youca{n}^{\prime }tseeme$
$Youca{n}^{\prime }tseeme.$$Youca{n}^{\prime }tseeme$
$Youca{n}^{\prime }tseeme.$$Youca{n}^{\prime }tseeme$