[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;
}