rt,90

1.04s 气si我了

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3010;
int a[N], dp[N][N / 10], dis[N][N];
int main() {
    int n, v;
    scanf("%d%d", &n, &v);
    for (register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	stable_sort(a + 1, a + n + 1);
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
			dis[i][j] = dis[i][j - 1] + a[j] - a[(i + j) / 2];
    for (int i = 0; i <= n; ++i)
		dp[i][1] = dis[1][i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= min(v, i); ++j)
            for (int k = j - 1; k <= i - 1; ++k)
				dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k + 1][i]);
    printf("%d", dp[n][v]);
    return 0;
}

求优化