在 P4767 中，暴力可以过，但很灵异：

#include <bits/stdc++.h>
using namespace std;

const int N = 3012, M = 312;
int n, m, a[N], dp[N][M], dis[N][N];

main() {
	scanf("%d %d", &n, &m);
	for (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, j; i <= n; ++i) for (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, j, k; i <= n; ++i) for (j = 1; j <= min(m, i); ++j) for (k = j - 1; k <= i - 1; ++k)
		dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k + 1][i]);
	return printf("%d", dp[n][m]), 0;
}

是能过的，但：

#include <bits/stdc++.h>
using namespace std;

const int N = 3012, M = 312;
int n, m, a[N], dis[N][N], dp[N][M];

main() {
	scanf("%d %d", &n, &m);
	for (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, j; i <= n; ++i) for (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, j, k; i <= n; ++i) for (j = 1; j <= min(m, i); ++j) for (k = j - 1; k <= i - 1; ++k)
		dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k + 1][i]);
	return printf("%d", dp[n][m]), 0;
}

只有 70pts。

你会发现只有定义不同：

70pts：

int n, m, a[N], dis[N][N], dp[N][M];

100pts：

int n, m, a[N], dp[N][M], dis[N][N];

对，就调换一下顺序就 AC 了。

而且快了很多，一个 1.20s+，一个 959ms。

还有，如果把 const int N = 3012 改成其他任何数都 AC 不了，比如 3001，3007，3010，3011，甚至 3011 和 3013 都过不了，只能 3012。

M 也一样，但 N = 3012，M = 3012 or 3014 是可以过的，M = 3011 或 3013 或 3015 都过不了，

这不存在评测浮动问题，我交了几遍，而且一个 1.20s+，一个 980ms-，差了很多。

我的提交记录

我会在回复中补充