6
18
2015
2

6.18模拟赛:Garen的反抗(revolt)

题目描述

    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);
}

 

 

Category: 随笔 | Tags: | Read Count: 4706
CoolSprng 说:
Jun 18, 2015 10:01:36 PM

看不懂→_→不过还是赞

阿毛 说:
Oct 21, 2015 04:59:38 PM

wpcap,水成这样真的好么>.<


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com