描述
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
输入第1行为m和n，其间用空格间隔
第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如
10 3
2 4 6 5 2 4 3 1 3
表示在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
因为不可能出现二号到四号上学，三号到一号上学的情况，即一个学校就会形成一个区间（没有重叠），于是我们用dp[m][n]表示在1至m的村庄中建立n所小学的最短路程。
对于每一个dp[x][y]都有几种情况：1，在村庄x建立第y所小学，此时dp[x][y]=dp[x-1][y-1]。2，在村庄x-i(x-i>=1)至村庄x的地方建立第y所小学(意思是：让村庄x-i(x-i>=1)至村庄x都到y上学)，
此时出现一个问题，究竟应该建立在（x-i）至x的哪个位置，很容易想到枚举，但有更优的方法：在村庄1-5中建一所小学，应该建在（1+5）/2的位置上，可以自己去推理，我懒不写推理过程了。
于是dp[x][y]=dp[x-i-1][y-1]+在（x+x-i+1）/2建小学的路程（可以不加一，只是我算路程要求我必须加），还有一个优化，比如我们算出了在x-i到x中建一所小学的路程数，
那么x-i-1到x中建一所小学的路程数就等于x-i到x的路程数+x-i-1到本次小学的距离。
预处理时将dp[n][m]值为无限大，但dp[1][1--m]=0,dp[2--n][1]用前面说过的一种方法推出来。
其次用前缀和更好算距离。
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 int cnt_cun=0,cnt_scl=0; 8 int jv[505]={0}; 9 int dp[505][505]={0}; 10 void dpdt( ); 11 12 13 void dpdt( ){ 14 memset(dp,0x7f,sizeof(dp)); 15 dp[0][0]=0; 16 for(int x=1;x<=cnt_scl;x++)dp[1][x]=0; 17 int now_size=0,next_size=1; 18 for(int x=2;x<=cnt_cun;x++){ 19 now_size=(1+x)/2; 20 dp[x][1]=dp[x-1][1]+jv[x]-jv[now_size]; 21 next_size=now_size; 22 } 23 24 25 for(int x=2;x<=cnt_cun;x++){ 26 for(int y=2;y<=cnt_scl;y++){ 27 if(y>=x){dp[x][y]=0;break;} 28 int fewr=dp[x-1][y-1],next_sze=x,next_jv=0; 29 for(int z=x-1;z>=1;z--){ 30 int now_sze=(1+x+z)/2; 31 int now_jv=next_jv+abs(jv[z]-jv[now_sze]); 32 next_sze=now_sze; 33 next_jv=now_jv; 34 if(now_jv+dp[z-1][y-1]<fewr)fewr=now_jv+dp[z-1][y-1]; 35 } 36 dp[x][y]=fewr; 37 } 38 } 39 return; 40 } 41 42 43 int main(){ 44 cin>>cnt_cun>>cnt_scl; 45 for(int x=2;x<=cnt_cun;x++){ 46 int a=0;cin>>a; 47 jv[x]=jv[x-1]+a; 48 } 49 50 dpdt( ); 51 cout<<dp[cnt_cun][cnt_scl]; 52 53 54 55 56 }
因为本人新手不会写题解，程序写的丑，看得懂大犇别喷我。
看不懂的额可以问我。