<min/max,+>卷积与背包优化

· · 算法·理论

【前置知识】

convex 与 concave：这是对于数组的概念。类比函数，下凸就是 convex，上凸就是 concave。

【<min,+>卷积问题】

考虑两个数组 a_{1\sim n},b_{1\sim m}，定义它们的<min,+>卷积结果 c：

因为普通的卷积是 \sum +，形式类似。所以这种运算就叫做<min,+>卷积。<max,+>卷积的定义是类似的。

这个问题目前没有快于 O(nm) 的解法，但是在特殊情况下可以做一些优化。

【双 convex 情况】

结论：如果 a,b 都 convex，可以 O(n+m) 解决这个问题。

考虑 a,b 的差分数组 \Delta a,\Delta b。（\Delta a_1=a_1，\Delta a_i=a_i-a_{i-1}） 则 c_i 就是在 \Delta a,\Delta b 中最小的 i 个数之和。

容易证明，不再赘述。

【单 convex 情况】

结论：如果 a 是任意数组，b 是 convex 的，可以做到 O(n\log m) 解决。

这个情况比上面的复杂很多。我们先定义一下两个函数方便叙述。

f_j(x)=\{(j+i,a_j+b_i)|1\le i\le m\} f(x)=\{(i,b_i)|1\le i\le m\}

观察 1：c_i 实际上等于 x=i 处，f_{1\sim n}(x) 最低点的值。 观察 2：f_j(x) 是 f(x) 的平移。

于是求 c 数组，实际上等价于求 f_{1\sim n}(x) 的下凸壳。下面讲解怎么求。

由观察 2 知 f_j(x) 与 f_{j'}(x) 最多一个交点（j\neq j' 时）。有了这个观察能做什么？

其实这里已经可以用李超线段树做了，不过李超树是 O(n\log^2 n) 的，我们像四边形不等式的队列那样，进一步优化。

维护队列 q 保存 i_1,i_2,\dots,i_k，表示当前还有用的函数图像有 f_{i_1\sim i_k}(x)。现加入 f_j(x)。若 f_j(x) 与 f_{i_k}(x) 的交点在 f_{i_k}(x) 与 f_{i_{k-1}}(x) 的交点左侧，则 i_k 没有用了，可以弹出。进行完所有弹出后，假设此时队列末尾元素为 k（如果队列弹空了就直接加入 j）。在 f_k(x) 有用的区间内二分，找到第一个 f_k(x)\le f_j(x) 的位置 pos。从 pos 往后，f_k(x)\le f_j(x)。

在具体实现时，除了记录 i_1，还要记录它的有用区间 [l_{i_1},r_{i_1}]。这和四边形不等式的二分队列是一样的。

二分带一个 \log m，而函数个数是 n，所以总复杂度是 O(n\log m) 的。

【背包优化】

【01 背包优化】

记总重量为 C，重量种类数为 m，这里给出一个 O(n\log n+mC\log C) 的做法。

把物品按重量从大到小排序，同重量按价值从大到小排序。

令 A_i[j] 表示考虑完前 i 种重量后，选一些物品总重为 j 的最大价值。

从 A_{i-1} 怎么推到 A_i？设第 i 类重量为 w。用 B[k] 表示在第 i 类中选总重为 kw 的物品（其实就是选 k 个）的最大价值。

观察发现 B[k] 是 concave 的。因为 B[k+1] 比 B[k] 选多一个物品，而且这多的一个物品必然是价值第 k+1 大的物品。再多选一个，就是第 k+2 大的了。以此类推，增长的价值必然递减。

把 A_{i-1}[j] 按 j\bmod w 的余数分类，每一类单独与 B 做<max,+>卷积，就能得到对应位置的 A_{i}[j]。每一类 A 的长度是 \dfrac{C}{w}，B 的长度是 w，一共做 w 次（余数分 w 类）。所以复杂度是 O(\dfrac{C}{w}\log w\cdot w)=O(C\log w)=O(C\log C)。

注意这里不能直接把 B 拓展到长度为 C 的数组，然后拿这个拓展后的数组卷。因为拓展后 B 显然就不 concave 了。

一共 m 种重量，所以复杂度是 O(mC\log C)。排序还有 O(n\log n)。总复杂度 O(n\log n+mC\log C)。

【完全背包优化】

这个优化和<max,+>卷积凸优化没关系。

设最大重量为 D，总重 C，给出一个 O(D^2\log C) 的解法。基于倍增。

令 ans_i 表示总重为 i 时的最大价值。暴力求出 ans_{0}\sim ans_{2D}，复杂度 O(D^2)。

有：当 i>D，ans_i=\max_{|j-k|\le D,j+k=i}(ans_j+ans_k)。

进而可以得到：ans_{j-D/2\sim j+D/2} 和 ans_{k-D/2\sim k+D/2} 做一次<max,+>卷积可以得到 ans_{j+k-D\sim j+k+D}。我们只需要 O(D^2) 的来做这个就够了。

既然 O(D^2) 可以从 j,k\rightarrow j+k，那么直接倍增就可以做到 O(D^2\log C)。