题解：CF571B Minimization

endswitch · 2024-10-16 14:36:42 · 题解

模 k 意义下分组，可以分为个数为 \lfloor \frac{n}{k} \rfloor, \lfloor \frac{n}{k} \rfloor + 1 两组。

再贪心地想，要使 \displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}| 最小，直接排序是一定最优的。因为去交换邻项可以反证出答案一定更大。

设 dp_{i, j} 为选上述第一种组别 i 次，选第二种组别 j 次的最小值，对于每个划分的组都是可以拆贡献为末项减首项的，于是就很好转移了。

代码：

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

const int N = 3e5 + 5;
const int M = 5e3 + 5;
int n, k, a[N], dp[M][M];

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> a[i];

    sort(a + 1, a + 1 + n);

    int len = n / k, m1 = n % k, m2 = (n - m1) / len - m1;

    memset(dp, 0x3f, sizeof dp);

    dp[0][0] = 0;

    for(int i = 0 ; i <= m1 ; ++ i)
        for(int j = 0 ; j <= m2 ; ++ j) {
            int now = i * (len + 1) + j * len;

            if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[now] - a[now - len]);
            if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[now] - a[now - len + 1]);
        }

    cout << dp[m1][m2];

    return 0;
}