ACM模版

描述

题解

这个题,打眼一看就是贪心,然后我就贪心写了一下, WA 了三分之一,分析了一下,感觉只是贪心不行,还有 dp 搞搞才行……

首先,贪心的思路是,我们需要将数据分为 k 组,其中有 n % k 组的大小为 nk+1 ,剩下的 kn % k 组有 nk 个。这个好理解,就不多说了,接着我们要将序列排序,因为当我们这样分组时,最后结果其实就是各组最小花费的和,而各组的最小花费当然是选取若干个排序后是连续的数最佳,加减抵消后的结果就是每组最后一个数减去第一个数,当然,也就是最大的数减去最小的数。此时,剩下的问题就很明朗了,排序后的数组如何划分为上述 k 组使其和最小?这个部分自然就是动归了。

其实,这里的第二部分我们不用动归也未尝不可,用 dfs 搜索也许也是可以的,因为我们可以肯定的是,每次划分一段区间作为一组数的时候,都要贪心的从左右两侧划分,所以控制好未划分区间即可。一直到划分完后,判断一下结果是否更优,当然,这种方法并不是特别好,时间消耗可能比较高,记忆化一下能提升一些效率,但是还是不如 dp 省事儿,实在是下策。

也许,上边就是我在胡诌,并不可行吧……懒得尝试了。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 3e5 + 10;
const int MAXK = 5e3 + 10;

int n, k;
int A[MAXN];
int dp[MAXK][MAXK];

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0; //EOF
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scan_d(A[i]);
    }
    sort(A, A + n);

    int t1 = n % k;
    int t2 = k - t1;
    k = n / k;

    dp[0][0] = 0;
    for (int i = 1; i <= t2; i++)
    {
        dp[i][0] = dp[i - 1][0] + A[i * k - 1] - A[(i - 1) * k];
    }
    for (int j = 1; j <= t1; j++)
    {
        dp[0][j] = dp[0][j - 1] + A[j * (k + 1) - 1] - A[(j - 1) * (k + 1)];
    }

    int k1, k2;
    for (int i = 1; i <= t2; i++)
    {
        for (int j = 1; j <= t1; j++)
        {
            k1 = (i - 1) * k + j * (k + 1);
            k2 = i * k + (j - 1) * (k + 1);
            dp[i][j] = min(dp[i - 1][j] + ((k1 + k) > n ? 0 : (A[k1 + k - 1] - A[k1])),
                           dp[i][j - 1] + ((k2 + k + 1) > n ? 0 : (A[k2 + k] - A[k2])));
        }
    }

    printf("%d\n", dp[t2][t1]);

    return 0;
}