题解：AT_abc310_h [ABC310Ex] Negative Cost

· · 题解

题外话：vp 的时候看知乎被抓了，教练惩罚我讲这道题。

一个典（？）的背包优化

好的这个东西一看就很背包，但是容量太大了。对于这种大容量小代价的背包有一个做法（也是今天才学到的，但是教练说之前讲过 n 次了（大雾））。

我们考虑贪心，选性价比最优的方案。但是正常情况下不能直接贪，因为会有一部分容量浪费掉，你选的一些最优性价比物品可能会导致这些部分无法利用。

欸？我枚举浪费掉的部分然后剩下的跑贪心不就行了？

但是我们注意到这样一个问题，就是如果不用性价比最高物品填充的容量太大了怎么办？

证明：设物品的最大代价为 L，性价比最高的物品代价为 x，证明你不用性价比最高物品的数量上界为 L。

显然由于是完全背包，所以代价一样的物品直接取最优价值就好了。那么如果选择了 L+1 个性价比不高的物品，我们把这些东西的代价做一个前缀和，设他为 s，根据鸽巢原理显然有 s_x\equiv s_y\pmod {x} ，这一段拿 x 填充显然更优。

那么你做容量在 L^2 以内的背包，然后枚举代价剩下的用性价比最高的填充即可。

回到这道题

好的我们得到了一个做法，但是我们发现根本不能直接套上去。

原因在于我们约束的是法力值，但是要最优化的是操作次数。

那我们能不能把法术组合一起，然后就不管法力只管次数了呢？

下文称 \max c 为 L。

我们称一个操作序列是合法的，当且仅当 \forall x,\sum_{i=1}^{x} c_{i}\ge 0。也就是说任何时候法力不会小于 0（注意，这里的 c 取过反）。

我们称一个操作序列是优秀的，当且仅当他合法并且 \forall x,\sum_{i=1}^{x} c_{i}\le 2L。

称一个法术组是优秀的，当且仅当他的长度小于等于 2L 且排成操作序列后是优秀的。

证明：每一个合法操作序列都可以拆成若干优秀操作序列。

对于每一个 c_x<0 的位置，一直往前交换直到 s_x\le 2L。显然一直这样操作下去合法性不会改变，而这样操作完之后剩下的 s_x>2L 的位置即以后都没有 c_y<0(x<y)。那这些位置就单独拆出来。

证明：优秀操作序列可以拆成若干优秀法术组。

根据鸽巢原理，对于长度大于 2L 的优秀序列存在 s_x=s_y(x\not = y)。把这一段拆出来显然这段可以重排成优秀的并且不影响剩下的部分。

那么我们拆出来了若干长度在 2L 以内的优秀序列，把他们拍成法术组就好了。

好的那么我们每一个操作序列都可以用若干优秀法术组表示。这些法术组可以随意调换位置和多次使用。

那我们背包要保留的物品本质上是一堆法术组。这些法术组最多有 2L 种代价，等价于 2L 种物品做背包，那我们接下来的事情就是求出这些法术组。

完成

这个法术组合直接做一个背包就好了，约束一下背包的魔法和以及次数和不能超过 2L。然后现加入正法力的再加入负法力的法术。

证明一下在背包过程也只需要把魔法和控制在 2L，大概就是你魔法和超过了 2L 那你以后肯定是要拿负法力法术去补的（如果你不补那这个法术组合就不优秀了）。但是要是补的话你只需要 2L 的法力就可以保证你不会出现不合法的状况。

那你就得到了 2L 个法术组，按照最开始的方法做背包就好了。

Link.