题解：P10971 Cookies

· · 题解

首先考虑贪心邻项交换，设有 i，j 两个人，他们的 g 固定，饼干数 a 大的给 g 更大的一个人才能使总怨气更少，所以降序排序 g。然后考虑 dp 的状态，常规的，f_{i,j} 表示前 i 个人花费 j 块饼干的最小怨气，怎么转移呢？对于 a_i<a_{i+1} 的，直接加上 i\times g_i 即可，那如果 a_i=a_{i+1} 呢？我们还要计算末尾饼干数相等的个数才能转移，在这种 dp 状态下很难快速维护（话说好像可以 O(n) 维护，跟输出方案一样？）。所以我们可以考虑枚举后几位 a 全为 1 的情况，具体来说就是：

f_{i,j}=\min_{0\le k<i}\{f_{k,j-(i-k)}+k\times\sum_{p=k+1}^{i}g_{p}\}\tag1

其中 f_{k,j-(i-k)}+\sum_{p=k+1}^{i}g_{p} 表示最后 k+1\sim i 的位置只有一个饼干的怨气值，枚举 k 从而转移到 f_{i,j}。这样就解决了吗？其实并没有，还要和 f_{i,j-i} 取 \min 才行。这一类状态也是合法的转移状态。为什么呢？考虑缩放状态。可以发现将前 i 个人的饼干数全都加减一个数时，由于相对大小不变，怨气值是不变的，所以有 f_{i,j}=f_{i,j-i}，因为我们在计算 f_{i,j} 时，所有的 f_{i',j'(i'\le i,j'<j)} 都是已知的，所以可以转移，那要不要考虑 f_{i,j-2\times i} 呢？并不用，因为这个状态已经包含在 f_{i,j-i} 了，而 f_{i,j-i} 又转移到了 f_{i,j} 了。

在输出方案时是最有趣的地方，解决了我看书做题时不懂的地方（输出方案是书上没有涉及的）。首先根据常规套路，用 pre 数组记录方案的转移，然后递归输出，得到：

0 0
2 2
2 4
3 5
3 8
3 11
3 14
3 17
3 20

啊，这是什么意思？仔细理解一下，发现当 i 相等时，是通过 f_{i,j}=f_{i,j-i} 转移的；而当 i 变化时，是通过上面的 (1) 式进行的转移，那最终的 a 数组是多少呢？再想一下，通过第一种转移过来的就相当于将 a_{1\sim i} 全部加 1，而当 i 变化时，就是将 a_{i_1+1}\sim a_{i_2+1} 全部加 1（在前 i 个数固定的情况下，再将这后面的数变成 1，现在反着变回去）。什么意思？模拟一下：

i j     a[1~3]  
0 0     0 0 0
2 2     1 1 0 // 转移过程: i = 2 时,在 0 0 0 的基础上将最后 2 位改为 1
2 4     2 2 0 // 转移过程: i = 2 时,在 1 1 0 的基础上全部增加 1
3 5     2 2 1 // 转移过程: i = 3 时,在 2 2 0 的基础上将最后 1 位改为 1
3 8     3 3 2 // 转移过程: i = 3 时,在 2 2 1 的基础上全部增加 1
3 11    4 4 3 // 以此类推...
3 14    5 5 4
3 17    6 6 5
3 20    7 7 6

这样就很好理解了转移的过程，递归时修改用前缀和就行。

#include <bits/stdc++.h>
#define LL long long
#define fq(i,d,u) for(int i(d); i <= u; ++i)
#define fr(i,u,d) for(int i(u); i >= d; --i)
using namespace std;
const int N = 35, M = 5e3+5;
struct from {
    int i, j;
} pre[N][M];
struct node {
    int v, id;
} g[N];
int n, m, f[N][M], s[N], idx[N], ans[N];
// 前 i 个人,花费 j 个饼干的最小怨气
bool cmp(node a, node b) {
    return a.v > b.v;
}
void back(from p, from fa) {
    if (p.i == fa.i) idx[1]++, idx[p.i + 1]--;
    else idx[p.i + 1]++, idx[fa.i + 1]--;
    if (p.i == 0) return ;
    back(pre[p.i][p.j], p);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    fq(i, 1, n) cin >> g[i].v, g[i].id = i;
    sort(g + 1, g + 1 + n, cmp);
    fq(i, 1, n) s[i] = s[i - 1] + g[i].v;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    fq(i, 1, n) fq(j, i, m) {
        int ret = f[i][j - i];
        pre[i][j] = {i, j - i};
        fq(k, 0, i - 1) { // 枚举 k ~ i 都为 1 的 f 最小值
            int val = f[k][j - (i - k)] + k * (s[i] - s[k]);
            if (val < ret) {
                ret = val;
                pre[i][j] = {k, j - (i - k)}; // (i - k) 表示 后面 1 的费用
            }
        }
        f[i][j] = min(f[i][j], ret);
    }
    cout << f[n][m] << '\n';
    back(pre[n][m], from {n, m});
    fq(i, 0, n) idx[i] += idx[i - 1];
    fq(i, 1, n) ans[g[i].id] = idx[i];
    fq(i, 1, n) cout << ans[i] << ' ';
    return 0;
}