题目链接:https://loj.ac/p/6039
有\(n\)个物品，第\(i\)个费用为\(w_i\)，价值为\(v_i\)，对于\(k\in[1,m]\)求费用为\(m\)时能获得的最大价值。
\(1\leq n\leq 10^6,1\leq m\leq 5\times 10^4,1\leq w_i\leq 300,1\leq v_i\leq 10^9\)
好早以前写的不过不知道为啥错了，现在来补个新的。
\(w_i\)很小，考虑以其为突破口，显然地我们可以把\(w_i\)相同的按照\(v_i\)从大到小排序，那么对于每个\(w_i\)，我们就可以选择若干个。
设\(f_{i,j}\)表示做到\(w=i\)时费用为\(j\)的最大价值和，那么有
\[f_{i,j}=f_{i-1,j-ki}+s_{i,z}
\]
（\(s_{i,z}\)表示\(w=i\)的物品中前\(z\)大的价值和）
这个式子很难用常规的优化，但是可以用四边形不等式。至于证明，我们有\(w_{i,j}=s_{j-i}\)
要证明
\[w_{i,j}+w_{i+1,j+1}\geq w_{i,j+1}+w_{i+1,j}
\[s_{j-i}+s_{j-i}\geq s_{j-i+1}+s_{j-i-1}
然后因为\(s_{i+1}-s_{i}\)是递减的，所以成立。
那么我们现在对于每个枚举的\(w=i\)，把所有的\(ik+j(\ j\in[0,i)\ )\)都分成一组。
然后对于每一组我们都用四边形不等式优化，不过我忘了优化的方法了，还是记一下吧：
对于所有的可能的决策我们用一个单调队列记录，顺带记录\(z_i\)表示队列里第\(i\)个决策和第\(i+1\)个决策的交叉点（在\(z_i\)之前\(q_{i}\)更优，\(z_i\)以之后\(q_{i+1}\)更优）。
然后每次弹出队列前面的来找答案，加入的时候我们就二分出队尾和新加入的决策交换点，然后一直弹尾部直到不交叉。
时间复杂度：\(O(mw\log m)\)