求：在村庄内建邮局，要使村庄到邮局的距离和最小。
设有m个村庄，分别为 V1 V2 V3 … Vm， 要建n个邮局，分别为P1 P2 P3 … Pn。
在DP的问题中，经常有从m个物体中选n个物体的情况，本题显然也属于这种情况。一般可以这样考虑：假设已经选了1个，那么就成了在m-1个中选n-1个的问题了。
对于此题，也可以考虑先建一个邮局。建在哪里呢？不妨设，该邮局建在Vk+1..Vm之间的某个村庄里，而且规定Vk+1..Vm之间再不允许建立其他邮局了。因此，剩下的n-1个邮局必然出现在V1..Vk之间的村庄内，这样问题就转换成：在前k个村庄里选n-1个邮局的问题。
设dp( m,n )表示在V1…Vm之间建立n个邮局时的最短距离。
L( i, j )表示在Vi…Vj之间建立一个邮局的最短距离。
状态转换方程：
dp( m,n ) = Min( dp( k,n-1 ) + L( k+1,m ) ), 其中：1 <= k<m
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int V_MAX = 305;
const int P_MAX = 35;
const int INF = 9999999;
//dis[i][j] means smallest sum dis when build a post office in villages from i to j
int dis[V_MAX][V_MAX];
//dp[i][j] means smallest sum dis when build j post offices in villages from 1 to i
int dp[V_MAX][P_MAX];
int vnum,pnum;
int vpos[V_MAX];
void solve()
{
//compute dis
memset(dis,0,sizeof(dis));
int i,j;
for(i=1;i<=vnum;i++)
{
for(j=i+1;j<=vnum;j++)
{
int mid = (i+j) >> 1;//build a post office at middle village can get smallest sum dis
for(int k=i;k<=j;k++)
dis[i][j] += abs(vpos[k]-vpos[mid]);
}
}
for(i=1;i<=vnum;i++)
dp[i][0] = INF;
for(i=1;i<=vnum;i++)
{
for(j=1;j<=pnum&&j<i;j++)
{
int min = INF;
for(int k=j-1;k<i;k++)
if(dp[k][j-1] + dis[k+1][i] < min)
min = dp[k][j-1] + dis[k+1][i];
dp[i][j]=min;
}
}
cout<<dp[vnum][pnum]<<endl;
}
int main()
{
//freopen("1160.txt","r",stdin);
cin>>vnum>>pnum;
for(int i=1;i<=vnum;i++)
cin>>vpos[i];
solve();
}
此题分析转载自 http://blog.csdn.net/sj13051180/article/details/6669737