记录编号	147014	评测结果	AAAAAAAAAA
题目名称	[SPOJ 699] 巨大的背包	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2015-01-22 18:34:57	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long L;
L T,N,S,Y,C,zj1,zj2,i,p,mainV=1,mainW=0,limit;
L f[1010]={0},w[20]={0},W[2000]={0},nw[1010]={0};

void init()
{
	scanf("%lld%lld%lld%lld",&N,&S,&Y,&C);
	for(i=1;i<=N;i++)
	{
		scanf("%lld%lld",&zj1,&zj2);
		if(w[zj2]<zj1)w[zj2]=zj1;
	}
	for(i=1;i<=18;i++)
	if(w[i]*mainV>i*mainW)
	mainW=w[i],mainV=i;
	limit=17*mainV;
}

void work()
{
	//第一次完全背包求出limit+20限制下各数所对应最大值
	zj1=limit+20;
	for(i=1;i<=18;i++)
	for(p=i;p<=zj1;p++)
	if(W[p-i]+w[i]>W[p])W[p]=W[p-i]+w[i];
	//第二次完全背包求出limit限制下合并1~limit个背包所对应最大值
	for(i=1;i<=limit;i++)
	{
		zj1=(i*Y-limit)/mainV;
		zj2=zj1*mainW+W[i*Y-zj1*mainV];
		nw[i]=zj2-C*(i-1);
	}
	//第三次完全背包求出f
	for(i=1;i<=limit;i++)
	for(p=i;p<=S;p++)
	if(f[p-i]+nw[i]>f[p])f[p]=f[p-i]+nw[i];
	printf("%lld\n",f[S]);
}

void End_()
{
	mainV=1,mainW=0;
	memset(w,0,sizeof(w));
	memset(W,0,sizeof(W));
	memset(nw,0,sizeof(nw));
	memset(f,0,sizeof(f));
}

int main()
{
	freopen("hugeknapsack.in","r",stdin);
	freopen("hugeknapsack.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		init();
		work();
		End_();
	}
	//while(1);
	return 0;
}