记录编号	444565	评测结果	WWWWWWWWWW
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	0
用户昵称	CSU_Turkey	是否通过	未通过
代码语言	C++	运行时间	0.215 s
提交时间	2017-09-03 11:54:41	内存使用	16.65 MiB

#include<bits/stdc++.h>
using namespace std;
int n,w[105],c[105],m,f[105][40005],v[105];
int head=1,tail;
struct ghb{
	int val,seat;
}que[40005];
int read(){
	int a=0;
	char ch=getchar();
	while(!(ch<='9'&&ch>='0'))ch=getchar();
	while(ch<='9'&&ch>='0'){
		a=(a<<1)+(a<<3)+ch-'0';
		ch=getchar();
	}
	return a;
}
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
//	freopen("1.txt","r",stdin);
	que[0].val=0x3fffffff;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		v[i]=read();
		w[i]=read();
		c[i]=read();
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<w[i];j++){
			head=0,tail=0;
			for(int k=j;k<=m;k+=w[i]){
				int now=f[i-1][k]-(k/w[i])*v[i];
				if(now<=que[tail].val){
					que[++tail].val=now;
					que[tail].seat=k/w[i];
				}
				else{
					while(que[tail].val<now&&head<=tail){//head<=tail很有必要，不然head假如已经到了10了，tail却继续往10之前找，就不合法了 
						tail--;
					}
					que[++tail].seat=k/w[i];
					que[tail].val=now;
				}
				if(que[head].seat+min(c[i],k/w[i])<k/w[i]){
					head++;
					if(head>tail)que[tail].val=0x3fffffff;//这里表示如果队列空了，就给tail附一个极大值，保证下一个元素能一定进队
					//但后来我发现好像没必要，因为上面给了特判，如果队列空了，就不进入while了 
				}
				f[i][k]=que[head].val+k/w[i]*v[i];
			}
		}
	}
	cout<<f[n][m];
	return 0;
}