upd 2025/7/12：更新了一些错别字。 题目传送门

题意

把 $n$ 个数分成 $m$ 个区间，使得每个数与所在区间的中位数之差的总和最小，输出这个最小值。

思路

先排序，明显的 DP：

• 定义状态：$f_{i,j}$ 表示前 $i$ 个区域使用 $j$ 种颜色的最小误差。
• 设 $color(l,r)$ 为区间 $l$ 到 $r$ 为一个颜色时的误差。我们枚举一个 $k$，从 $k$ 到 $j$ 为一个新的颜色，而 $f_{k,j-1}$ 为 $1$ 到 $k$ 使用 $j-1$ 种颜色，把它们相加，刚好是 $f_{i,j}$，所以我们只需要在这里求个最小值就可以了
• 状态转移：$f_{i,j}=\begin{cases} 0 & \text{ if } i=0,j=0 \\ f_{k,j-1}+color(k+1,i) & \text{ if } i>0,j>0 \end{cases}$
• 优化：这里每次 $color(l,r)$ 需要遍历一次 $l$ 到 $r$，于是我们可以考虑前缀和优化。细节看代码。

代码

记得开 long long。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[3010];
long long sum[3010], f[3010][20];
long long color(int l, int r)
{
    int mid = (l + r) / 2;
    return a[mid] * (mid - l) - (sum[mid - 1] - sum[l - 1]) + sum[r] - sum[mid] - a[mid] * (r - mid);
}
int main()
{
	scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &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));
    printf("%lld", f[n][m]);
	return 0;
}

给个赞再走吧。 题目传送门