题目描述
一些村庄被建在一条笔直的高边公路边上。我们用一条坐标轴来描述这条高边公路，每一个村庄的坐标都是整数。没有两个村庄坐标相同。两个村庄问的距离，定义为它们坐标值差的绝对值。
我们需要在一些村庄建立邮局一一当然，并不是每一个村庄都必须建立邮局。邮局 必须被建在村庄里，因此它的坐标和它所在的村庄坐标相同。每个村庄使用离它最近的 那个邮局，建立这些邮局的原则是:所有村庄到各自所使用的邮局的距离总和最小。你的任务是编写一个程序，在给定了每个村庄的坐标和将要建立的邮局数之后，按照上述原则，合理地选择这些邮局的位置。
输入
第一行包含两个整数:第一个整数是村庄的数目 V，1≤V≤300;第二个整数是将建立的邮局数 P，1≤P≤30 且 P≤V。
第二行按照递增顺序列出了 V 个整数。这 V 个整数分别表示了各村庄的位 置坐标。对于每一个位置坐标 X，1≤X≤10000。
输出
第一行是一个整S，表示你所求出的所有村庄到离它最近邮局的距离的总和。
样例输入
10 5 1 2 3 6 7 9 11 22 44 50
样例输出
9
提示
在2 7 22 44 50建立邮局
题解：
先处理出dis[i][j]数组，表示i到j中建一个邮局需要的总路程，很明显一个区间中选中间位置会使总路程最小.
然后就是简单DP：F[i][k]表示前i个村庄建k个邮局最小的总路程.
F[i][k]=min(F[j][k-1]+dis[j+1][i],F[i][k]); k是枚举的邮局数量.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=,M=,INF=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int x[N],dis[N][N],F[N][M];
int main()
{
int n=gi(),p=gi(),mid;
for(int i=;i<=n;i++)x[i]=gi();
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
mid=(i+j)>>;
for(int k=i;k<=j;k++)
dis[i][j]+=abs(x[mid]-x[k]);
}
}
memset(F,/,sizeof(F));
for(int i=;i<=n;i++)F[i][]=dis[][i];
for(int k=;k<=p;k++)
{
F[k][k]=;
for(int i=k+;i<=n;i++)
{
for(int j=k-;j<i;j++)
{
F[i][k]=min(F[j][k-]+dis[j+][i],F[i][k]);
}
}
}
printf("%d",F[n][p]);
return ;
}