记录编号	444605	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.264 s
提交时间	2017-09-03 15:09:27	内存使用	17.87 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;

int n,l,v[110],m[110],w[110],f[110][40010];

struct nodes
{
	int tim,large;
}q[100010];

int qh=1,qt=1;

int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&l);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&m[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<w[i];j++){
			qh=qt=1;
			for(int k=0;k*w[i]+j<=l;k++){
				int nl=f[i-1][k*w[i]+j]-k*v[i];
				while(q[qt-1].large<nl&&qh<qt){
					qt--;
				}
				q[qt].large=nl;
				q[qt].tim=k;
				qt++;
				while(q[qh].tim+min(m[i],k)<k){
					qh++;
				}
				f[i][k*w[i]+j]=q[qh].large+k*v[i];
			}
		}
	}
	printf("%d\n",f[n][l]);
	return 0;
}
/*
f[i][j]=max(f[i-1][j-k*w[i]]+k*v[i])(0<=k<=m[i])
因为j=j%w[i]+j/w[i]*w[i]
得出f[i][j]=max(f[i-1][j%w[i]+j/w[i]*w[i]-k*w[i]]+k*v[i])(0<=k<=m[i]) 
设a=j%w[i],b=j/w[i]-k
则k=j/w[i]-b
f[i][j]=max(f[i-1][a+b*w[i]]+(j/w[i]-b)*v[i])(j/w[i]-m[i]<=b<=j/w[i])
对每个等式右侧减去(j/w[i])*v[i]再加上(j/w[i])*v[i]
f[i][j]=max(f[i-1][a+b*w[i]]-b*v[i])+(j/w[i])*v[i](j/w[i]-m[i]<=b<=j/w[i])
把循环改为枚举i,a,j/w[i]
于是对于每个j求出当j/w[i]-m[i]<=b<=j/w[i]时f[i-1][a+b*w[i]]-b*v[i]中的最大值
即可以使用单调队列在O(1)求出 
*/