记录编号	41649	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.540 s
提交时间	2012-08-07 12:12:34	内存使用	78.42 MiB

#include <cstdio>
using namespace std;

int f[40001],w[10000001],v[10000001],squ[10000]={1};

int main(void)
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	int i,j,temp,n,W,c=0,vt,wt,mt;
	for (i=1;i<10000;i++)
		squ[i]=2*squ[i-1];
	scanf("%d%d",&n,&W);
	for (i=0;i<n;i++)
	{
		scanf("%d%d%d",&vt,&wt,&mt);
		for (j=0;squ[j]<=mt;j++)
		{
			v[c]=vt*squ[j];
			w[c]=wt*squ[j];
			c++;
			mt-=squ[j];
		}
		if (mt)
		{
			v[c]=vt*mt;
			w[c]=wt*mt;
			c++;
		}
	}
	for (i=0;i<c;i++)
		for (j=W;j>=w[i];j--)
		{
			temp=f[j-w[i]]+v[i];
			if (f[j]<temp)
				f[j]=temp;
		}
	printf("%d\n",f[W]);
	return(0);
}