【题解】洛谷P1776 宝物筛选 [单调队列优化多重背包]
二进制优化还是不够快，如果我们想时间复杂度为 ，还得找新的方法。
（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;
}