1197：山区建小学

秒速五厘米 2022-01-07 08:11 159阅读 0赞

### 1197：山区建小学 ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 1428 通过数: 983

### 【题目描述】 ###

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

### 【输入】 ###

第1行为mm和nn，其间用空格间隔

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

例如:

10 3
    2 4 6 5 2 4 3 1 3

表示在1010个村庄建33所学校。第11个村庄与第22个村庄距离为22，第22个村庄与第33个村庄距离为44，第33个村庄与第44个村庄距离为66，...，第99个村庄到第1010个村庄的距离为33。

### 【输出】 ###

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

### 【输入样例】 ###

10 2
    3 1 3 1 1 1 1 1 3

### 【输出样例】 ###

> ###  这是一个区间DP问题。 ###

f\[i\]\[j\]表示在前i个村庄建立j所学校，各村庄到最近学校的距离和的最小值。

f\[i\]\[j\]=min(f\[i\]\[j\],f\[k\]\[j-1\]+c\[k+1\]\[j\])

在前k个村庄造j-1个学校的最小和   +   k+1到i个学校造一个学校的最小和

[https://www.cnblogs.com/caiyishuai/p/8600874.html][https_www.cnblogs.com_caiyishuai_p_8600874.html]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

#include<cstdio>
    #include<cmath>
    #include<iostream>
    using namespace std; 
    int a[505][505],c[505][505],f[505][505];
    int main()
    {
    	int m,n;
    	scanf("%d%d",&m,&n);//m个村，n个小学
    	for(int i = 1; i < m; ++i)
    		scanf("%d",&a[i][i+1]);//相邻两个村之间的距离
    	for(int i = 1; i <= m; ++i)//i,j两地的距离 
    	{
    		for(int  j = i+1; j <= m; ++j)
    		{
    			a[i][j] = a[j-1][j] + a[i][j-1];
    			a[j][i] = a[i][j];
    		}
    	} 
    	int mid;
    	for(int i = 1; i <= m; ++i)
    	{
    		for(int j = i+1; j <= m; ++j)
    		{
    			mid=(i+j)/2;//`在两地中间建小学时，距离最短 
    			c[i][j] = 0;//c[i][j]表示两地到最近学校的距离和 
    			for(int k = i; k <= j; ++k)
    				c[i][j] += a[k][mid]; 
    		}
    	} 
    	//f[i][j]表示从i个村庄中建立j个学校，村庄到学校的最短距离和 
    	for(int i = 1; i <= m; ++i)
    		f[i][1] = c[1][i];
    	int s = 0x7fffffff; 
    	for(int i = 1; i <= m; ++i)
    	{
    		for(int j = 2; j <= n; ++j)
    		{
    			f[i][j] = s;
    			for(int k  = j-1; k <= i; ++k)
    				f[i][j] = min(f[i][j],f[k][j-1]+c[k+1][i]);
    		}
    	 } 
    	printf("%d",f[m][n]);
    	return 0;
    }

[https_www.cnblogs.com_caiyishuai_p_8600874.html]: https://www.cnblogs.com/caiyishuai/p/8600874.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20211227/361df9281ece4664ad33051426049956.png