本文共 2763 字，大约阅读时间需要 9 分钟。

$$山区建小学$$

题目链接：

题目

政府在某山区修建了一条道路，恰好穿越总共$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 23 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
   
    #include
    
     #include
     
      #include
      
       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$

转载地址：http://jlph.baihongyu.com/