WTRC's Memory

题目描述

    Garen很疼自己的妹妹Lux。Lux也知道哥哥疼她，整天骑在他的头上作威作福。终于有一天，Garen忍不住了，他准备反抗！！

    然而，虽然Garen是一个很强的战士，但是他的妹妹Lux可是整个Billycia最杰出的光明魔法师，战斗力爆表。他一个人显然是对付不了Lux的，因此，他决定找上N个兄弟一起，反抗Lux的残暴统治。

    为此，他还制造了一部威武霸气的”Billy战车”。这辆战车的最大载重量为M。现在他想知道他们能不能反抗成功。

【输入文件】

    第一行有三个数N,M,K。N表示盖伦找来了N个兄弟，M表示”Billy”战车最大载重量为M，K表示Lux的战斗力。

    之后N行，每行两个数Wi,Zi,分别表示第i个兄弟的质量和战斗力。

【输出文件】

    共2行。第一行，若能反抗成功（大于等于），输出”succeed”;若不能成功，输出”fail”。第二行输出最高战斗力。

【样例输入】

3 10 10

7 10

6 9

1 2

【样例输出】

succeed

12

【样例解释】

    选1、3两个兄弟。

【数据规模】

    对于20%的数据，1<=N,M,K<=1000,1<=Wi,Zi<=10;

    对于100%的数据,1<=Wi,Zi<=10,1<=N,M<=100000,K<=300000。

好，童鞋们先想一想怎么搞……题解在下面

Analysis:

    这其实是一道傻逼题。这题裸的01背包只能过20分。看上去N<=100000很唬人，其实有了Wi，Zi<=10这个条件，一共的情况总数也就100种，那么也就是说相当于只有100种物品，每种物品有若干件。

    然而这似乎看上去没有什么卵用？不，并不是！这样，我们在枚举每种物品取几件时就可以把它用类二进制的方法去做01背包，复杂度可以降到log级别。

    最坏的时间复杂度为O(M*max{Wi}*max{Zi}*log(N/(max{Wi}*max{Zi}))。

    下面是我打的标程：

//WTRC - revolt
#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int f[1000005],n,m,k,a[11][11],Test;
inline int read(){
	int ch=getchar(),x=0;
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
void ZeroOnePack(int weight,int value){
	for (int i=m;i>=weight;i--)
		f[i]=max(f[i],f[i-weight]+value);
}
int main(){
	freopen("revolt.in","r",stdin);
	freopen("revolt.out","w",stdout);
	n=read(),m=read(),k=read();
	memset(a,0,sizeof(a));
	for (int i=1;i<=n;i++){
		int w=read(),v=read();
		a[w][v]++;
	}
	memset(f,128,sizeof(f));
	f[0]=0;
	for (int i=1;i<=10;i++)
		for (int j=1;j<=10;j++){
			int k=1;
			while (a[i][j]>=k){
				ZeroOnePack(i*k,j*k);
				a[i][j]-=k;
				k*=2;
			}
			if (a[i][j]) ZeroOnePack(i*a[i][j],j*a[i][j]);
		}	
	int Ans=0;
	for (int i=0;i<=1000000;i++)
		Ans=max(Ans,f[i]);
	if (Ans>=k) puts("succeed");
		else puts("fail");
	printf("%d\n",Ans);
}