自动搬运

查看原文

来自洛谷，原作者为

	youyou2007 如果你已选择生命，那便是选择了活下去。 活在这个世界，见证这个世界。体验它，并真切地接受这最后的每一个当下。

搬运于2025-08-24 22:15:42，当前版本为作者最后更新于2020-10-23 11:32:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一、思路

1、朴素转移

这题题目都讲了区间，明显的区间DP......

令$f[i][j]$ 表示考虑了前$i$ 个区域，已经用了$j$ 种颜色的最小误差

则枚举 $k$, $f[i][j]$ 一定是从前k个区间的最小值再加上从$k+1$ 至 $i$ 的区间误差，

状态转移方程式：$f[i][j] = min(f[i][j], f[k][j - 1] + color(k + 1, i))$ ，其中$color$ 即为区间误差之和。

时间复杂度：$O(N ^ 3M)$

很明显，这个巨大的复杂度会T飞，所以需要一些优化

2、求值优化

再思考优化$color$ ，可以先前缀和$sum$ 求出每一段的人口数，而中位数即为排好序后中间两个数的平均数。

所以区间误差之和不难得出，可以得到以下$O(1)$ 的柿子：

$a[mid] * (mid - l) - sum[mid - 1] + sum[l - 1] - a[mid] * (r - mid) + sum[r] - sum[mid]$ ，（其中mid即为中间那个位置，不是中位数！）

所以可以把这一个柿子单独写个函数拉出来，可以将时间复杂度优化到$O(N ^ 2M)$

二、code

注意开始需要先排序，这样求中位数可以优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const int M = 15;
int n, m;
int f[N][M], sum[N], a[N];
int color(int l, int r)
{
	int mid = (l + r) / 2;//求中位数的位置
	return a[mid] * (mid - l) - sum[mid - 1] + sum[l - 1] - a[mid] * (r - mid) + sum[r] - sum[mid]; //O(1)优化
}              
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];//前缀和预处理
	}
	memset(f, 0x3f, sizeof f);//开始全赋最大值
	f[0][0] = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int k = 0; k < i; k++)
			{
				f[i][j] = min(f[i][j], f[k][j - 1] + color(k + 1, i));//转移方程
			}
		}		
	}
	cout << f[n][m];
	return 0;
}