ABC373F 题解

容易发现这是一个完全背包问题，我们设状态 \(f_{i,j}\) 表示前 \(i\) 个物品使用了 \(j\) 个容量的最大价值。

容易写出转移方程式：\(f_{i,j}=\max\limits_{k=0}^{\lfloor\frac{j}{w}\rfloor} f_{i-1,j-kw}+kv-k^2\)

直接 dp 是 \(O(n^3)\)。考虑对这个 dp 进行优化。

上面的方程容易写成滚动数组的形式。不妨设上一维状态为 \(g\)，这一维为 \(f\)。

Solution 1

将后面的 \(kv-k^2\) 记为 \(T(k)\)，则一段区间 \([l,r]\) 价值记为 \(w(l,r)\)，则 \(w(l,r)=T(r-l+1)\)。发现若对于决策点 \(a,a+1,b,b+1\)，始终满足 \(w(a,b)+w(a+1,b+1)\ge w(a,b+1)+w(a+1,b)\)。

将 \(j\) 按对 \(w\) 取模后的值分类后使用决策单调性优化即可。时间复杂度 \(O(n^2\log n)\)。

Solution 2

同样对 \(j\) 按对 \(w\) 取模后的值分类。改写 dp 式子：\(f_{i}=\max g_j+(i-j)v-(i-j)^2\)，对式子拆分：\(f_{i}=g_j+iv-jv-i^2-j^2+2ij\)，移项得 \(g_j-jv-j^2=-2ij+i^2+fi-iv\)，容易发现这是斜率优化的形式，且 \(k=2i\) 为单调上升的， \(x=i\)也是单增的，使用单调队列可以优化到 \(O(n^2)\)。