CH5105:Cookies 题解

主要思路

显然，这是一道动态规划的题目。这道线性 DP 的方程极其难推，因为在正常推的情况下，总要考虑状态前的状态才能进行 DP。然而，这道题有一个思路清奇的方法。

首先是预处理部分：我们需要把孩子的愤怒值按升序排列，并且记录每一个孩子前后的序号映射。

bool compare(const ll &a, const ll &b)
{ 
    return g[a] > g[b]; 
}

scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
    scanf("%lld", &g[i]), c[i] = i;
sort(c + 1, c + n + 1, compare);

状态表示很容易想出，\(dp[i][j]\)代表给前\(i\)个人分配了\(j\)块饼干。不过 DP 的过程非常的神奇，考虑两个分支

• 其一就是把前\(i\)个人的饼干都取走一个，加在第\(i\)个小孩身上，这样的话前面的愤怒值其实相对来讲是不变的，可直接转移\(dp[i][j] = dp[i][j-i]\)。
• 之后我们再来考虑把中间的段分开来考虑取走的问题。我们可以枚举一个端点\(k \in [0,i)\)，然后我们可以设区间\([1,k]\)不动，从区间\([k+1,i]\)中取走若干个曲奇。这样的话应该这样转移：\(dp[i][j] = min\{ dp[k][j-(i-k)]+k*\sum^{i}_{p=k+1}g[p]\}\)。我们可以写成前缀和形式：\(dp[i][j] = min\{ dp[k][j-(i-k)]+k*(sum[i]-sum[k])\}\)。

这样我们就搞定了 DP 部分。我们还需要统计饼干数量，可以考虑在转移过程中记录一些信息来搞定尾处理。

代码

// CH5105.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 35, MX_M = 5100;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, g[MX_N], dp[MX_N][MX_M], c[MX_N], presum[MX_N];
ll lastPersonNum[MX_N][MX_M], cookieSum[MX_N][MX_M], ans[MX_N];
bool compare(const ll &a, const ll &b) { return g[a] > g[b]; }
void process(int num, int bis)
{
    if (num == 0)
        return;
    process(lastPersonNum[num][bis], cookieSum[num][bis]);
    if (lastPersonNum[num][bis] == num)
        for (int i = 1; i <= num; i++)
            ans[c[i]]++;
    else
        for (int i = lastPersonNum[num][bis] + 1; i <= num; i++)
            ans[c[i]] = 1;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &g[i]), c[i] = i;
    sort(c + 1, c + n + 1, compare);
    for (int i = 1; i <= n; i++)
        presum[i] = presum[i - 1] + g[c[i]];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int bis = i; bis <= m; bis++)
        {
            dp[i][bis] = dp[i][bis - i];
            lastPersonNum[i][bis] = i;
            cookieSum[i][bis] = bis - i;
            for (int k = 0; k < i; k++)
            {
                ll val = dp[k][bis - (i - k)] + k * (presum[i] - presum[k]);
                if (dp[i][bis] > val)
                    dp[i][bis] = val, lastPersonNum[i][bis] = k, cookieSum[i][bis] = bis - (i - k);
            }
        }
    printf("%lld\n", dp[n][m]);
    process(n, m);
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}