萌新第一天用 hydro，打开题库随了一道题，然后被这道题吓到了。

感觉自己写过，翻了一下自己的代码，贺了一份原题交过来，改了改过了。

不出所料搬了道论文原题，还改了数据范围，很有实力！（这么有实力的吗

估计自己讲的不够清楚，SMAWK 不会的自己翻 2017 论文集。

考虑对每种体积的物品做 DP，设做完上一种物品后体积为 $i$ 的最大价值为 $g_i$，当前物品体积为 $v$，对这些物品排序后前 $j$ 个的价值和为 $s_{j}$。

为了更符合决策单调性的形式我们设 $w_{i,j}=s_{j-i+1}$，当 $i>j$ 时 $w_{i,j}=0$。

设做完当前 DP 值后体积为 $i$ 的最大价值为 $f_i$，显然有转移 $f_j=\max{g_i+w_{i,j}}$。

对于 $w$ 的定义考虑可以简单推出四边形不等式，即 $w_{i,j}+w_{i+1,j+1}\ge w_{i,j+1}+w_{i+1,j}$，于是有决策单调性。

但一般的做法都带 $\log$，这里给出其中一种：每次选取奇数列下去递归，找到决策点后单调指针求出偶数列的决策点往回传，层数 $\log$，每层 $O(n)$。

考虑优化，设当前有 $m$ 列，则此层有用的决策点只有 $m$ 个，每次把 $n$ 行都传下去显然不优。

采用 reduce 过程将 $2m\times m$ 的单调矩阵裁成 $m\times m$，考虑点 $(i,i)$，其贡献为 $g_i+w_{i,i}$。

将其与点 $(i+1,i)$ 比较，若当前点更优则 $i+1$ 行无用，一直裁到底使得只剩下 $m$ 个决策行，然后完成了 reduce 操作。

于是每层就只与当前大小 $m$ 有关了，用主定理计算一下 $T(n)=T(\frac n2)+O(n)$ 即知这是线性的。

以下用题目字母分析复杂度：故总复杂度 $O(m\times|\{w_i\}|)$，较差的实现可能出现 $O(m\log m)$ 的复杂度。

论文题难度降到 9 了，应该不能怪我吧（悲

其实难度还真不一定高，在线 SMAWK 才难一点。