时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 16MB，其他语言 32MB
描述
高速公路旁有一定数量的村庄。高速公路可被视为一整数轴，村庄位置与整数坐标对应。没有两个村庄在同一坐标上，两村庄的距离为坐标差的绝对值。现将邮局建在村庄上，即表示邮局与村庄有相同的位置。构建过程中，邮局的位置应使得所有村庄与其最近邮局的距离之和最小。
编写一程序，用给定位置的村庄和邮局数量，计算出村庄与其最近邮局的距离和的最小值。
输入描述
程序从标准输入读取。
第一行包含一个整数tcase，表示测试组数。
每组输入数据占两行。
第1行包含两个整数:村庄V（V < = 300）和邮局P的数量（1 < = P < = 30,P < = V）.
第2行包含V个整数，即村庄的位置X（1 < = X < = 10000）
输出描述
每行包括一个整数，即距离和的最小值。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,pos[3005],w[3005][3005],dp[3005][305],s[3005][3005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&pos[i]);
sort(pos+1,pos+1+n);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
w[i][j]=w[i][j-1]+pos[j]-pos[(i+j)/2];
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=s[i][j-1];k<i;k++)
{
if(dp[i][j]>dp[k][j-1]+w[k+1][i])
{
dp[i][j] = dp[k][j-1]+w[k+1][i];
s[i][j] = k;
}
}
}
}
cout<<dp[n][m];
return 0;
}
