记录编号	233769	评测结果	AAAAAAAAAA
题目名称	[SPOJ 699] 巨大的背包	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-03-05 19:30:15	内存使用	0.33 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int SIZEV=20,SIZEW=610;
typedef long long LL;
int N,S,C;
LL Y;
int maxw[SIZEW];
LL bestw=0,bestv=0;
void read()
{
	scanf("%d%d%lld%d",&N,&S,&Y,&C);
	int w,v;
	memset(maxw,0,sizeof(maxw));
	for(int i=1;i<=N;i++) 
	{
		scanf("%d%d",&w,&v);
		maxw[v]=max(maxw[v],w);
	}
}
LL kna[SIZEW];
LL maxme[SIZEW];
LL f[1010];
LL limit=0;
LL get(LL x)
{
	LL	t=(x-limit)/bestv;
	//cout<<x<<" "<<t<<" "<<x-t*bestv<<endl;
	return t*bestw+kna[x-t*bestv];
}
void DP()
{
	bestv=1;bestw=maxw[1];
	for(int i=2;i<SIZEV;i++) if(bestw*i<bestv*maxw[i]) bestw=maxw[i],bestv=i;//寻找密度最大的雕塑
	limit=(SIZEV-1)*bestv;
	//cout<<bestv<<" "<<bestw<<" "<<limit<<endl;
	//cout<<limit<<endl;
	memset(kna,0,sizeof(kna));
	for(int i=1;i<=limit+20;i++) for(int j=0;j<=i;j++) kna[i]=max(kna[i],kna[i-j]+maxw[j]);
	//for(int i=1;i<=limit;i++) cout<<i<<" "<<kna[i]<<endl;
	maxme[0]=0;
	for(int i=1;i<=limit;i++) maxme[i]=get(Y*i)-C*(i-1);
	//for(int i=1;i<=limit;i++) cout<<i<<" "<<maxme[i]<<" "<<endl;
	memset(f,0,sizeof(f));
	for(int i=1;i<=limit;i++)
	{
		for(int j=i;j<=S;j++) f[j]=max(f[j],f[j-i]+maxme[i]);
	}
	printf("%lld\n",f[S]);
}
int main()
{
	freopen("hugeknapsack.in","r",stdin);
	freopen("hugeknapsack.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T)
	{
		T--;
		read();
		//cout<<N<<" "<<S<<" "<<Y<<" "<<C<<endl;
		DP();
	}
	return 0;
}