题解：P10967 [IOI2000] 邮局（原始版）

思路

首先将坐标排序。

定义 \(dp_{i,j}\) 为前 \(i\) 个村庄放 \(j\) 个邮局的前 \(i\) 个村庄的最小距离总和，\(f(i,j)\) 表示村庄区间 \([i,j]\) 内放一个村庄时该区间的总和。

转化式易得 \(dp_{i}{j}=dp_{k}{j-1}+f(k+1,i),k\in [0,i)\)。

则本题的难点就为求 \(f(k-1,i)\)。

基本的数学知识，若村庄数为奇数，放中位数处距离和最小。若村庄为偶数，放中间两个村庄之间任意一处均可。

于是就得到了一个 \(O(PV^{3})\) 的做法。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3010,N=310;
int V,P,X[MAXN],dp[MAXN][N];
int f(int l,int r) {
	int mid=l+r>>1,ans=0;
	for(int i=l;i<mid;i++) ans+=X[mid]-X[i];
	for(int i=mid+1;i<=r;i++) ans+=X[i]-X[mid];
	return ans;
}
int main() {
	cin>>V>>P;
	for(int i=1;i<=V;i++) cin>>X[i];
	sort(X+1,X+V+1);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int j=1;j<=P;j++) {
		for(int i=1;i<=V;i++) {
			for(int k=0;k<i;k++) {
				dp[i][j]=min(dp[k][j-1]+f(k+1,i),dp[i][j]);
			}
		}
	}
	cout<<dp[V][P]<<endl;
	return 0;
}