[题]宝物筛选 #单调队列优化

五、宝物筛选（洛谷P1776）

题目链接

好家伙，找到了一个之前学习多重背包优化时的错误……
之前记的笔记还是很有用的……

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n, m; 
int v, w, s;
int lim;
int head, tail;
struct Q{//位置， 对应的底数(base number = basenb) int pos, bn;
}q[N];//q记录的是不同mod数的组里面的底数的最大值（以及它的位置）int main(){cin >> n >> m;for(int i = 1; i <= n; i ++){scanf("%d%d%d", &w, &v, &s);//按照不超过体积的每个数作为底数//既然枚举的是组数，那么不同组之间是不会被相互影响到的。for(int modd = 0; modd < v; modd ++){head = 0, tail = -1;//数量 for(int k = 0; k * v + modd <= m; k ++){//当前位置，以及对应的底数（now base number 缩写成 nb ） int nowpos = k * v + modd, nbn = f[nowpos] - k * w;//头不在范围内了就弹出队头//不在范围内就是说：总的s的数量的体积已经无法触及到底数的对应位置了，//也就是bpos = 1,但是k = 4, s = 2，此时就是k的长度无法涉及的范围了。if(q[head].pos < k - s && head <= tail) head ++;while(q[tail].bn <= nbn && head <= tail) tail --;//队尾 ,这里的pos之前写错了……但是在某wing上还是过了……water。q[++ tail].pos = k, q[tail].bn = nbn;f[nowpos] = max(f[nowpos], q[head].bn + k * w);}}}cout << f[m];return 0;
}