定制网站建设公司电话,合肥网站优化 新浪博客,网页传奇排行,中国菲律宾铁路项目五、宝物筛选#xff08;洛谷P1776#xff09;
题目链接 好家伙#xff0c;找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #includebits/stdc.h
using namespace std;
const int N 1e5 10;
int f[N];
int n, m;
int v, w, s;
int l…五、宝物筛选洛谷P1776
题目链接 好家伙找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #includebits/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;
}
