http://acm.pku.edu.cn/JudgeOnline/problem?id=1160用opt[i][j]记录把前i个邮局建到前j个村庄中的最优解
用cost[i][j]记录所有在i到j村庄中，建1个邮局的最小代价。显然邮局应该设到中点。
让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)
#include"stdio.h"
long cost[301][301];
long opt[301][301]; //把前i个邮局建到前j个村庄中的最优解
int v[301];
void pre(int m,int n)
{
int i,j,mid,k; //记录所有在i到j村庄中，建一个邮局的最小代价。显然邮局应该设到中点。
for (i=1;i<=m;i++)
for(j=i;j<=m;j++) //j>=i
{
cost[i][j]=0;
mid=(i+j)/2;
for(k=i;k<=mid;k++)
cost[i][j]+=v[mid]-v[k];
for(k=mid+1;k<=j;k++)
cost[i][j]+=v[k]-v[mid];
}
}
void main()
{
int i,j,k;
int m,n;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
scanf("%d",&v[i]);
pre(m,n);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
opt[i][j]=3000000;
opt[0][0]=0;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
if(opt[i][j]<3000000)
{
for(k=1;j+k<=m;k++)
if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k]) //状态转移. 让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1到第j+k个村庄。
opt[i+1][j+k]=opt[i][j]+cost[j+1][j+k];
}
printf("%d\n", opt[n][m]);
}