[ABC373F] Knapsack with Diminishing Values

AtCoder

比较遗憾，E 题用了太多时间了，没做出来。当时看到有平方感觉难道是斜率优化之类的？这下猜对了。
拜谢 WA90。
不过官解好像没用斜率优化？不会。

设 \(f_{i,j}\) 表示前 \(i\) 个物品一共用了 \(j\) 的体积。直接暴力做是三次方的。

当加入一个体积为 \(w\)，价值为 \(v\) 的物品时，就像单调队列优化多重背包一样，我们把 \(j\) 按照模 \(w\) 分组，只有组间会转移。然后开一个 vector \(g\)，把这些 \(f_{i-1,j}\) 扔进去，即 \(g_k=f_{i-1,j}(j=d+kw)\)，同样地设一个 \(h\) 对应新的 \(f_i\)，那么就有转移：

是我们喜欢的斜率优化。

把 \(f\) 还原就做完了。时间复杂度 \(\mathcal{O}(nW)\)。