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

五、宝物筛选（洛谷P1776）

题目链接

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39