#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;
}

• Re:复杂度应该是PV^3，不过前面系数不大 (47) mandycool 2012-08-14 13:04:28
• Re:好不容易ac了，贴个代码 (1239) acvg 2020-11-30 14:42:54