> #include<iostream>
> using namespace std;
> /**
> 思路：dp[p][v]表示的是0~v这v+1个村庄内，建立p个邮局时最小距离和；那么
> 	动态规划方程是 dp[p][v] = min( dp[p-1][k] + sum(k+1,v) ),k=(v-1)~0；
> 	sum(i,j)表示第i到第j个村庄共享1个邮局的最小距离和。
> 	最后输出dp[P][v-1]。
> **/
> namespace p1160{
> 	int V,P;
> 	const int NV=301,NP=31;
> 	int dp[NP][NV]; // 由于算第i层时只和i-1层相关，可用轮转数组替代
> 	int pos[NV]; //村庄坐标
> 	int calSum(int i,int j); //计算第i到第j个村庄共享1个邮局的最小距离和
> 	int minn(int i,int j){return i<j?i:j;}
> };
> using namespace p1160;
> int main(void){
> 	memset(dp,127,sizeof(dp)); //initial MAX
> 	cin>>V>>P;	
> 	for(int i=0;i<V;i++){ //初始化只有一个邮局的情况
> 		cin>>pos[i];
> 		dp[1][i] = calSum(0,i);
> 	}
> 	for(int i=2;i<=P;i++){
> 		for(int j=1;j<V;j++){
> 			for(int k=j-1;k>=0;k--){
> 				if(i-1>=k+1){ //more post office than village
> 					dp[i][j] = minn(dp[i][j],calSum(k+1,j));
> 					break;
> 				}
> 				else
> 					dp[i][j] = minn(dp[i][j],dp[i-1][k]+calSum(k+1,j));
> 			}
> 		}
> 	}
> 	cout<<dp[P][V-1];
> 	//system("pause");
> 	return 0;
> }
> 
> int p1160::calSum(int i,int j){ 
> 	int ans = 0;
> 	int pi=i,pj=j;
> 	while(i<j){	// 每次考虑最外层的2个村庄，邮局一定要建立在它们中间，最短距离为 pos[j]-pos[i]
> 		ans+=pos[j]-pos[i];
> 		i++; j--;
> 	}
> 	return ans;
> }