[CodeForces572D] Minimization(思维,贪心,DP)

题目链接:https://codeforces.com/contest/572/problem/D

题意:给你$n$个数的数组$a$,要求你对这个数组重排,使得满足公式值最小:
$$
\sum_{i=1}^{n-k}|a[i]-a[i+k]|
$$

如果$k=0$的话那么我们对这个数组排序就好,如果排好序的话答案就是$a_n-a_1$,由此可见实际上中间结果对最终结果是没有影响的。

我们考虑首先对整个数组进行排序,考虑我们每隔$k$个就取一个数能组成多少数组,只有两种:

长度为$\dfrac{n}{k}​$的数组,有$n-n\%k​$个;长度为$\dfrac{n}{k}+1​$的数组,有$n\%k​$个。在这种情况下答案是各个数组的最大和最小数之差。我们现在可以考虑dp了,假如某个数$a_i​$放入第一类数组中,那么这个数对答案的贡献就是$a_i-a_{begin}​$,其中$a_{begin}​$是这个数组的开头数字。由于k<=5000,实际上述两种数组最多不超过5000个,定义$f(i,j)​$表示第一类数组有$i​$个,第二类数组有$j​$个时的上述公式的最小值,我们可以根据$i,j​$来计算两类数组分配时的$begin​$值,状态转移方程是:

$f[i][j] = min(f[i][j], f[i - 1][j] + a[i L1 + j L2] - a[(i - 1) L1 + j L2 + 1])$

$f[i][j] = min(f[i][j], f[i][j - 1] + a[i L1 + j L2] - a[i L1 + (j - 1) L2 + 1])$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using LL = long long;

const int maxn = 5050;
const int maxm = 300300;
int n, k, a[maxm];
LL f[maxn][maxn];

signed main() {
// freopen("in", "r", stdin);
while (cin >> n >> k) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int L1 = n / k, L2 = n / k + 1;
int n1 = k - n % k, n2 = n % k;
memset(f, 0x7f, sizeof f);
f[0][0] = 0;
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
if (i) f[i][j] = min(f[i][j], f[i - 1][j] + a[i * L1 + j * L2] - a[(i - 1) * L1 + j * L2 + 1]);
if (j) f[i][j] = min(f[i][j], f[i][j - 1] + a[i * L1 + j * L2] - a[i * L1 + (j - 1) * L2 + 1]);
}
}
cout << f[n1][n2] << endl;
}
return 0;
}