题解

首先预处理出i~j放一个邮局的最短距离dis[i][j],dp[j][i]表示前i个村庄放了j个邮局的最短距离

$dp[j][i]=min(dp[j-1][k]+dis[k+1][i])$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=307;
int dp[N][N],dis[N][N],x[N],n,m;
inline void init(){
	memset(dp,0x3f,sizeof dp);
	rep(i,1,n)scanf("%d",&x[i]);
	sort(x+1,x+n+1);
	rep(i,1,n)rep(j,i+1,n)dis[i][j]=dis[i][j-1]+x[j]-x[i+j>>1];
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		init();
		rep(i,1,n)dp[1][i]=dis[1][i];
		rep(j,2,m)rep(i,1,n)rep(k,1,i-1)dp[j][i]=min(dp[j][i],dp[j-1][k]+dis[k+1][i]);
		printf("%d\n",dp[m][n]);
	}
	return 0;
}