题意
有 \(n\) 个物品, 每个物品体积为 \(s_i\), 价值为 \(v_i\), 求背包容量为 \(1,2,\cdots m\) 时最大价值.
\(n\le 1e6,m\le 1e5,s\le 300,v\le 1e9\)
时空限制 \(5s,512MB\)
题解
普通01背包复杂度 \(O(nm)\), 无法满足 \(n\le 1e6,m\le 1e5\). 发现 \(s\le 300\),可以考虑把 \(s\) 相同的扔到一起更新. 这样这道题变得类似于多重背包 , 区别在于多重背包每个物体的价值相同 , 但本题中物体价值不保证相同 .
多重背包的优化方式有两种 , 一种是二进制拆分 , 一种是单调队列 . 这道题由于价值不同 , 如果用二进制拆成若干组 , 会存在某种可能 , 需要的几个物体不能被表示出来 .
尝试单调队列 , 先把朴素列出来
\[f_i= \sum_{j}^{} f_j+sum_{(i-j)/w} \]其中 \(w\) 代表当前考虑的体积 , \(sum_k\) 表示当前体积下前 \(k\) 大的价值和 .
模仿多重背包的单调队列做法 , 把 \(i\) 按照 \(\mod k\) 的值分类处理 . 对于每一类用一个单调队列维护可行范围内的最大的 \(f_j+sum_{(i-j)/w}\) .
分析单调性 : 设 \(i\) , \(j\) 是两个决策点 , 要更新 \(f_k\) 时 , \(i\) 不优于 \(j\) , 要求满足
\[f_i+ sum_{(k-i)/w}\ge f_j+sum_{(k-j)/w} \]这时发现 , 维护的这个值并不符合单调性,因为当前更新的位置 \(k\) 变化的时候 , \(i\) 与 \(j\) 之间所取的若干个价值会发生变化 . 但是这个变化具有一种单调性 . 随着 \(k\) 的增大 , 用 \(f_i\) 来更新比 \(f_j\) 更新能多取的几个物品的价值递减 . 因此存在一个时刻 \(t\) , 使得 \(k<=t\) 时 \(f_i\) 更优 , 而 \(k>t\) 时 \(f_j\) 更优 .
对于每一对 \(i,j\) , 在 \(k>t\) 时 , \(i\) 就没有用了 , 我们需要把 \(i\) 从队列中扔掉 . 时刻 \(t\) 在原序列中并不单调 , 但是对于三个决策点 \(i,j,k\) , 若 \(t_{i,j}\ge t_{j,k}\) ,当 \(i\) 从队列中扔掉的时候 \(j\) 已经应该被扔掉 . 也就是说我们只需要维护一个 \(t\) 递增的决策点序列就可以了 .
仍然使用单调队列维护 , 维护的是前后的 \(t\) 的单调性 .
每次一个新决策点 \(i\) 入队 , 如果队列 \(q\) 中 \(t_{q_{top-1},q_{top}} \ge t_{q_{top},i}\) , 说明当前的 \(top\) 无用 , 把它扔掉 , 直到队头扔不掉 , 再把 \(i\) 加入.
标签：le,题目,队列,sum,01,背包,top,单调 From： https://www.cnblogs.com/youlv/p/18438068