自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:02:33，当前版本为作者最后更新于2018-06-17 12:03:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这明显是一道$DP$题。通过观察$n$，$m$的范围（$500$）可得，题目要求在$O(n^3)$的时间复杂度内完成状态转移。

我们设计$dp[i][j]$表示在前$i$个村庄中建立$j$个小学的最小距离总和。设$f[i][j]$表示在村庄区间$[i,j]$中（从第$i$个村庄到第$j$个村庄，包括两边）只建$1$座小学的最小距离总和。那么我们可以得到状态转移方程：

$dp[i][j]=min\{dp[k][j-1]+f[k+1][i]\}$

这样我们计算出$f$数组，就可以在$O(n^2\times m)$的时间复杂度内完成状态转移了。

那么问题来了：怎样计算$f[i][j]$呢？

（这里需要一点直觉）在区间$[i,j]$内建一所小学，当然是要建在正中间，这样可以保证方案最优。所以，我们只需要选择区间的中点，即编号为$mid=\frac{i+j}2$的点，然后计算出所有村庄到该点的距离，即

$f[i][j]=\sum_{k=i}^j |distance(k,mid)|~~~(mid=\frac{i+j}2)$

$f[i][j]$的计算的时间复杂度为$O(n^3)$

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510;
const int inf=2e9;
int n,m,a[maxn],f[maxn][maxn],dp[maxn][maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)scanf("%d",a+i),a[i]+=a[i-1];
	for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)
	{
		int mid=(l+r)>>1;
		for(int k=l;k<=r;k++)f[l][r]+=abs(a[mid]-a[k]);
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		if(j>i){dp[i][j]=0;continue;}
		for(int k=j-1;k<=i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+f[k+1][i]);
	}
	printf("%d\n",dp[n][m]);
	return 0;
}