max-plus 卷积优化背包

<min, +> 卷积

对于一个卷积式子 \(C_i = \min_j(A_j + B_{i - j})\)，要求 \(B\) 为下凸包。令函数 \(f_j(x) = A_j + B_{x - j}\)。

考虑对于 \(g(x) = f_p(x) - f_q(x) = (A_p - A_q) + (B_{x - p} - B_{x - q})\)，若 \(p > q\)，我们有：

\[g(x + 1) - g(x) = (B_{x - p + 1} - B_{x - p}) - (B_{x - q + 1} - B_{x - q}) \leq 0 \]

于是 \(g\) 至多有一个零点，这意味着 \(f_p(x) = f_q(x)\) 至多在一个地方相交，并且 \(g\) 具有良好的单调性。

用一个队列维护这个过程，将函数不断插入队列。具体来说维护 \((id, L)\) 表示函数 \(f_{id}\) 从 \(L\) 开始生效。

每次我们不断对于队尾函数二分，如果新函数完全优于队尾就删除队尾函数，否则找出 \(pos\) 为最小的队尾函数比加入函数劣的位置将新函数加入队尾。其实就是一个正常单调队列的过程。

卷积优化 01 背包

将物品按照重量分类从大到小排序，同重量按价值从大到小排序。

令 \(A_i(j)\) 为考虑完前 \(i\) 类后总重为 \(j\) 的最大价值，现在需要优化从 \(A_{i - 1}\) 推到 \(A_i\) 的过程。

设 \(B_k\) 为第 \(i\) 类中选出前 \(k\) 个物品，那么 \(B_k\) 显然是凸的。此时的转移式子为 \(A_i(j) = \max \{A_i(j - kw) + B_k\}\)，这个 \(kw\) 非常难受。

我们将 \(A_{i - 1}(j)\) 按照 \(j \bmod w\) 分类即可，对于每一类单独做 <max, +> 卷积即可。

复杂度为 \(O(n\log n + wm\log m)\)。