自动搬运

查看原文

来自洛谷，原作者为

	HoshiuZ 生命潦草，我在弯腰。

搬运于2025-08-24 22:03:24，当前版本为作者最后更新于2020-02-25 19:22:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

首先将坐标排个序。

定义$dp[i][j]$表示前$i$个村庄放$j$个邮局的前$i$个村庄的最小距离总和，$w(i,j)$表示村庄区间$[i,j]$内放一个村庄时该区间的最小距离总和。

易得

$$dp[i][j]=\min\{dp[k][j-1]+w(k+1,i)\},k\in[0,i)$$

那么关键就在于$w(k+1,i)$的处理了。

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

于是便可得一个$O(PV^3)$的算法。

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310

using namespace std;

int V,P,X[MAXN],dp[MAXN][N];

int w(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]+w(k+1,i),dp[i][j]);
			}
		}
	}

	cout<<dp[V][P]<<endl;
	
	return 0;
}

再想想，可以提前预处理出$w$，其实这个$w$是可以$O(V^2)$递推出来的，根据放置一个邮局，邮局位置总是在中位数处，便可推得

$$w[l][r]=w[l][r-1]+X[r]-X[\lfloor\frac{l+r}{2}\rfloor] $$

于是又可以得到一个$O(PV^2)$的算法。

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310

using namespace std;

int V,P,X[MAXN],dp[MAXN][N],w[MAXN][MAXN];

void init() {
	for(int l=1;l<=V;l++) {
		w[l][l]=0;
		for(int r=l+1;r<=V;r++) {
			w[l][r]=w[l][r-1]+X[r]-X[l+r>>1];
		}
	}
}

int main() {
	cin>>V>>P;
	for(int i=1;i<=V;i++) cin>>X[i];
	
	init();
	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]+w[k+1][i],dp[i][j]);
			}
		}
	}

	cout<<dp[V][P]<<endl;
	
	return 0;
}

其实$w$是满足四边形不等式的。

由上面$w$的递推式，可得$w[l][r+1]-w[l][r]=X[r+1]-X[\lfloor\frac{l+r+1}{2}\rfloor]\ $①

那么$w[l+1][r+1]-w[l+1][r]=X[r+1]-X[\lfloor\frac{l+r+2}{2}\rfloor]\ $②

用①$-$②，得

$$X[r+1]-X[\lfloor\frac{l+r+1}{2}\rfloor]-(X[r+1]-X[\lfloor\frac{l+r+2}{2}\rfloor])=X[\lfloor\frac{l+r+2}{2}\rfloor]-X[\lfloor\frac{l+r+1}{2}\rfloor] $$

$X$坐标递增，则$X[\lfloor\frac{l+r+2}{2}\rfloor]-X[\lfloor\frac{l+r+1}{2}\rfloor]\ge 0$

即

$$w[l][r+1]-w[l][r]-(w[l+1][r+1]-w[l+1][r]) \ge 0$$ $$w[l][r+1]-w[l][r]-w[l+1][r+1]+w[l+1][r] \ge 0$$ $$w[l][r+1]+w[l+1][r] \ge w[l][r]+w[l+1][r+1]$$

因此$w$满足四边形不等式，且明显，对于$a\le b\le c\le d$，$w[a][d]\ge w[b][c]$，故$dp$满足四边形不等式。

因为$dp$满足四边形不等式，所以对于$dp[i][j]$的最优决策$d[i][j]$，$d[i][j-1]\le d[i][j]\le d[i+1][j]$

于是状态转移$dp[i][j]$时，从$[d[i][j-1],d[i+1][j]]$中找最优决策。

由于要用到$dp[i+1][j]$，所以倒序求解。

时间复杂度$O(PV)$。

代码

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310
#define INF 0x3f3f3f3f

using namespace std;

int V,P,X[MAXN],dp[MAXN][N],w[MAXN][MAXN],d[MAXN][N];

void init() {
	for(int l=1;l<=V;l++) {
		w[l][l]=0;
		for(int r=l+1;r<=V;r++) {
			w[l][r]=w[l][r-1]+X[r]-X[l+r>>1];
		}
	}
}

int main() {
	cin>>V>>P;
	for(int i=1;i<=V;i++) cin>>X[i];
	
	init();
	sort(X+1,X+V+1);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int j=1;j<=P;j++) {
		d[V+1][j]=V;
		for(int i=V;i>=1;i--) {
			int minn=INF,minid;
			for(int k=d[i][j-1];k<=d[i+1][j];k++) {
				if(dp[k][j-1]+w[k+1][i]<minn) {
					minn=dp[k][j-1]+w[k+1][i];
					minid=k;
				}
			}
			dp[i][j]=minn;
			d[i][j]=minid;
		}
	}

	cout<<dp[V][P]<<endl;
	
	return 0;
}