自动搬运

查看原文

来自洛谷，原作者为

	yzc1125 RE别枝惊鹊，CE半夜鸣蝉。TLE里说丰年，听取MLE声一片。七八个OLE,两三点UKE。旧时WAPE边，路转AC忽见。

搬运于2025-08-24 21:41:47，当前版本为作者最后更新于2025-08-19 00:17:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

思路

可以发现，这一题 $n,k \le 100$，是完全可以用 $O(n^3)$ 的，优先考虑动态规划。

可以发现这题中只有 $n,k$，所以可以定义 $dp_{i,j}$ 表示对前 $j$ 栋楼来说，建造 $i$ 所学校学生所走的距离和的最小值。

定义 $f_{i,j}$ 表示在 $i$ 到 $j$ 号楼之间，安置一所学校学生所走的距离和的最小值。那么就可以得出：

$$dp_{i,j}= \min\{dp_{i,j},dp_{i-1,k}+f_{k+1,j}\}$$

那么怎么求 $f$ 数组呢？可以发现假设这 $n$ 栋楼分别有 $x_1,x_2,x_3,\cdots,x_n$ 个学生，那么最短距离就是：

$$\sum_{i=1}^{n}x_i \cdot dis_{i,k}$$

那么为了使得距离和最小，所以 $x_i$ 应该平均分配，所以使得

$$\sum_{i=1}^{k} x_i \text{ 与} \sum_{i=k+1}^{n} x_i \text{ 的差最小} $$

找到这个 $k$ 之后，就可以将 $f$ 数组求出来了。

有了 $f$ 数组后，我们就可以求出 $dp$ 数组了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[120],b[120];
int s1[120][120],s2[120][120];//s1[i][j]表示i到j的学生人数，s2[i][j]表示i到j的距离
long long f[120][120];\\f[i][j]表示在i到j之间安置一所学校学生所走的距离和的最小值
long long dp[120][120];\\dp[i][j]表示对前j栋楼来说，建造i所学校学生所走的距离和的最小值
int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=2;i<=n;i++) cin>>b[i];
	for (int i=1;i<=n;i++)//计算学生人数区间
	{
		for (int j=i;j<=n;j++)
		{
			s1[i][j]=s1[i][j-1]+a[j];
		}
	}
	for (int i=1;i<=n;i++)//计算距离
	{
		for (int j=i+1;j<=n;j++)
		{
			s2[i][j]=s2[i][j-1]+b[j];
		}
	}
	memset(dp,0x3f,sizeof(dp));//赋极大值（用于找极小值）
	memset(f,0,sizeof(f));//清空
	for (int i=1;i<=n;i++)
	{
		for (int j=i;j<=n;j++)
		{
			for (int l=i;l<=j;l++)
			{
				if (s1[i][l]<s1[l+1][j]) continue;//找两边学生人数差最小的中点
				for (int k=i;k<=l;k++) f[i][j]+=a[k]*s2[k][l];
				for (int k=l+1;k<=j;k++) f[i][j]+=a[k]*s2[l][k];
//计算最短距离
				break;
			}
		}
	}
	for (int i=1;i<=n;i++) dp[1][i]=f[1][i];//初始化
	for (int i=2;i<=m;i++)
	{
		for (int j=i;j<=n;j++)
		{
			for (int l=i-1;l<=j-1;l++)
			{
				dp[i][j]=min(dp[i][j],dp[i-1][l]+f[l+1][j]);//状态转移方程
			}
		}
	}
	cout<<dp[m][n];//输出
}