二进制优化还是不够快，如果我们想时间复杂度为  ，还得找新的方法。

（W 为背包最大可承载量，N 为物品种类数）

例题：P1776 宝物筛选 - 洛谷

原来的转移式很普通：

注意到对于每个 ，有一个特定的取值范围。

而且答案是取该范围内的极值（最大或最小）。

最重要的，对于每个最优决策点 j - k * w，具有单调性，随着 i 的增长是单调递增的。

这种情况下可以用单调队列优化：

队首保存最优决策点，每次将不符合条件（超出范围）的队首弹出。

上面那个式子，可以化为：

整体：

而对于单种物体：

取值范围：

其实就是把原来式子里的  换成了 。

之所以要写成这一坨，

是要让  和  的格式一样，方便单调队列。

但是注意到 ，而不是 。

这是为什么呢？不会越界吗？

这是因为背包有个特点， 占背包的空间不一定就是 ，但一定比  小。

所以  也不一定就真的放了  个当前物品，只是长这个样子。

所以上面这整个式子，真正当前物品被放进去的个数是 。

把转移式化成这样，其实已经很快了。

但还能更快，我们知道   只跟  有关系。

也就是我们枚举 ，而  是  的余数。

讲了这么多，看看代码吧：

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 4e4 + 10;struct node {LL x;   //f[j + k * w] - k * vint k;   // k值
} q[N];LL f[N];int main() {ios::sync_with_stdio(false);cin.tie(0);int n; LL W;cin >> n >> W;LL sum = 0, ans = 0;for (int i = 1; i <= n; i++) {LL v, w; int m;cin >> v >> w >> m;if (w == 0) {      //如果这个宝物重量为 0，那就直接加上sum += v;continue;}int K = W / w;   //最大可选数量m = min(m, K);for (int j = 0; j < w; j++) {    //枚举余数 jint head, tail;    head = 1; tail = 0;    //队头队尾初始化LL r = (W - j) / w;    // k 的上限for (int k = 0; k <= r; k++) {while(head <= tail && f[j + k * w] - k * v >= q[tail].x) {tail--;     //当前 k 比队尾优而且比队尾后，踢队尾}tail ++;q[tail].k = k;                    // 记录物品数量q[tail].x = f[j + k * w] - k * v;    // 记录对应的 f 值while(head <= tail && k - q[head].k > m) {     //队头在不在可选域head++;}if (head <= tail) {f[j + k * w] = max(f[j + k * w], q[head].x + k * v);    //更新 fans = max(ans, f[j + k * w]);   //找最大的 f}}}}// f[W] + sum 也一样cout << sum + ans << "\n";return 0;
}