題目連結: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)\)