记录编号	42403	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.776 s
提交时间	2012-09-21 21:50:28	内存使用	3.30 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int N,W;
const int MAXN=111;
const int MAXM=44000;
class Mono
{
public:
	int v,w,n;
	vector<int> xishu;
}M[MAXN];
int F[MAXM]={0};

inline int Max(int a,int b) {return a>b?a:b;}

inline void init()
{
	scanf("%d%d\n",&N,&W);
	int tmp;
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d%d\n",&M[i].v,&M[i].w,&M[i].n);
		tmp=1;
		while(M[i].n-tmp+1>0)
		{
			M[i].xishu.push_back(tmp);
			M[i].n-=tmp;
			tmp*=2;
		}
		if(M[i].n>0) M[i].xishu.push_back(M[i].n);
		/*
		printf("%d ---> ",i);
		for(unsigned int j=0;j<M[i].xishu.size();j++)
			printf("%d ",M[i].xishu[j]);
		printf("\n");*/
	}
}

inline void pack()
{
	int noww,nowv;
	for(int i=1;i<=N;i++)
	{
		for(unsigned int j=0;j<M[i].xishu.size();j++)
		{
			nowv=M[i].v*M[i].xishu[j];
			noww=M[i].w*M[i].xishu[j];
			for(int k=W;k>=noww;k--)
				F[k]=Max(F[k],F[k-noww]+nowv);
		}
	}
	printf("%d\n",F[W]);
}

int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	init();
	pack();
	return 0;
}