记录编号	103619	评测结果	AAAAAAAAAA
题目名称	[SPOJ 699] 巨大的背包	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2014-05-29 20:30:37	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int SIZEV=610;
const int MXV=18;
ll vmaxw[SIZEV]={0};//体积为i,重量最大的雕像
//w是重量,v是体积
int N;
ll S,Y,C;//袋子数量,单个袋子容量,缝合袋子花费
ll limit;//当背包空间大于limit时,就继续填充主要填充物
ll bestw,bestv;//主要填充物的重量和体积
ll knapsack[SIZEV]={0};
ll mergemax[SIZEV]={0};//合并i个背包的最大收益
ll f[1010]={0};//有i个背包的最大收益
void merge_dp(void){
	memset(f,0,sizeof(f));
	for(int i=1;i<=limit;i++){//i个背包
		for(int j=i;j<=S;j++) f[j]=max(f[j],f[j-i]+mergemax[i]);
	}
}
ll getweight(ll K){//容量为K背包能装的最大重量
	ll t=(K-limit)/bestv;
	return t*bestw+knapsack[K-t*bestv];
}
void get_mergemax(void){
	mergemax[0]=0;
	for(int i=1;i<=limit;i++){
		mergemax[i]=getweight(Y*i)-C*(i-1);
	}
}
void get_snapsack(void){
	int n=limit+20;
	memset(knapsack,0,sizeof(knapsack));
	for(int i=1;i<=MXV;i++){//体积为i的物品
		for(int j=i;j<=n;j++){
			knapsack[j]=max(knapsack[j],knapsack[j-i]+vmaxw[i]);
		}
	}
}
void init(void){
	bestw=0,bestv=1;
	for(int i=1;i<=MXV;i++){//尝试体积为i的物品
		//如果vmaxw[i]/i>bestw/bestv,则更换
		if(vmaxw[i]*bestv>i*bestw) bestw=vmaxw[i],bestv=i;
	}
	limit=(MXV-1)*bestv;
}
void read(void){
	memset(vmaxw,0,sizeof(vmaxw));
	cin>>N>>S>>Y>>C;
	ll w,v;
	for(int i=1;i<=N;i++){
		cin>>w>>v;
		vmaxw[v]=max(vmaxw[v],w);
	}
}
int main(){
	freopen("hugeknapsack.in","r",stdin);
	freopen("hugeknapsack.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		init();
		get_snapsack();
		get_mergemax();
		merge_dp();
		printf("%lld\n",f[S]);
	}
	return 0;
}