自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:26:48，当前版本为作者最后更新于2020-11-28 17:01:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

欢迎到我的博客查看

两个多项式 $A$ 和 $B$ 通过 Mivik 卷积得到 $C$ 可以文字描述为：

两个盒子，从第一个里面选 $i$ 个（$0\le i<|A|$）物品权值为 $A_i$，从第二个里面选 $j$ 个（$0\le j<|B|$）权值为 $B_j$。$C_i$（$0\le i<|A|+|B|-1$）的值为从两个盒子里面选总共 $i$ 个的最大权值和。

容易证得 Mivik 卷积的结合律和交换律（考虑下标的和）。然后我们发现整个问题就变成了：

要求构造 $|S|-1$ 个物品，第 $i$ 个物品不选的权值为 $b_i$，选的权值为 $a_i$，使得从其中选 $i$ 个物品（$0\le i<|S|$）的最大权值和恰为 $S_i$。

我们考虑如果给定物品我们怎么计算 $S$。我们首先把所有的 $b_i$ 加起来得到 $S_0$，然后把所有物品按 $(a_i-b_i)$ 从大到小排序，则 $S_k$ 等于 $S_0$ 加上前 $k$ 大的 $(a_i-b_i)$。

我们发现 $S$ 合法当且仅当对于任意一个 $i$（$1\le i<|S|-1$），都有 $S_i-S_{i-1}\ge S_{i+1}-S_i$。我们可以用这个条件判合法。然后我们如下构造 $a$ 和 $b$ 数组（下标从 $1$ 开始）：$b_1$ 设置为 $S_0$，$a_1$ 设置为 $S_1$，对于其它的 $i$，$b_i$ 设置为 $0$，$a_i$ 设置为 $v_i-v_{i-1}$。注意对 $|S|=1$ 要特判答案。

所以这真的是一道良心语文题。

mivik.h

代码