自动搬运

查看原文

来自洛谷，原作者为

	liuChF **

搬运于2025-08-24 23:03:03，当前版本为作者最后更新于2024-10-04 19:33:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先考虑贪心邻项交换，设有 $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;
}