在v个村庄中建立p个邮局，求所有村庄到它最近的邮局的距离和，村庄在一条直线上，邮局建在村庄上。
思路：首先求出在连续的几个村庄上建立一个邮局的最短距离，用数组dis[i][j]表示在第i个村庄和第j个村庄之间建一个邮局的最短距。
!!!!!!!!!dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2]; （村庄位置为x[i]）
用数组dp[i][j]表示在前i个村庄中建立j个邮局的最小距离。即在前k（k<i）个村庄建立j-1个邮局，在k+1到j个村庄建立一个邮局。
dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i])
#include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define N 305 const int inf=0x3fffffff; int dp[N][35]; //在前i个村庄中建立j个邮局的最小耗费 int dis[N][N];//dis[i][j]：第i个村庄到第j个村庄建一个邮局的最短距离 int x[N]; //村庄位置 int main() { int v,p,i,j,k; while(scanf("%d%d",&v,&p)!=-1) { for(i=1;i<=v;i++) scanf("%d",&x[i]); //memset(dis,0,sizeof(dis)); for(i=1;i<=v;i++) { for(j=i+1;j<=v;j++) { dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2]; } } for(i=1;i<=v;i++) { dp[i][i]=0; //一个村庄一个邮局距离为零 dp[i][1]=dis[1][i]; //前i个村庄建立一个邮局 } for(j=2;j<=p;j++) { for(i=j+1;i<=v;i++) { dp[i][j]=inf; for(k=j-1;k<i;k++) { dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]); } } } printf("%d ",dp[v][p]); } return 0; }