`
tulunta
  • 浏览: 356797 次
文章分类
社区版块
存档分类
最新评论

HDU 3810 Magina (推荐)搜索+队列模拟背包

 
阅读更多

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

好题啊,前面好多是介绍dota里的这个英雄。。。可以忽略,到了最后一段才开始进入正题。

有n个地方有怪物,杀死每一个地方的怪物可以获得金钱gi,但是要花费ti的时间,英雄有个技能是瞬时移动,不需要花费时间,但是前提是两个地方之前是相连的。而且是无向的。升级需要金钱m,问满足升级条件的最短时间为多少。n的范围只有50,而且时限给了30s,乍一看肯定是搜索,估计大部分人也是写搜索的。yobobobo的搜索优化到10s左右,ORZ,应该还可以优化到1S以内。

这题是在ZeroClock的背包专题里发现了,便往背包上想,某个地方的怪只有两种选择,打或不打,有点类似背包。但是范围很大,升级经验达到10亿,也就是最大容量,完全超过了以往的背包,不论是时间上还是空间上都无法忍受。

其实题目就是一个无向图,有些顶点之间有路径。便形成一个个的连通子图,两个连通之图之间是无法互相移动的。也就是从一个子图开始,就只能在这些顶点之间随意移动。

问题转换成对于每一个连通子图里的怪物,杀或者不杀,也就是01背包,满足升级金钱的最小时间即可。

找出连通子图比较简单,dfs即可。

对于每一个子图的01背包,物品数量最多只有50,但是所需经验,背包容量太大。

其实在01背包的转移过程中,许多状态是用不上的,比如说取第一个物品的时候,其实在这之前的状态只有(0,0)即花费时间0,得到金钱0,其余的状态都没有用,而对于第一个物品只有杀或者不杀两种情况,不杀则还是(0,0),杀则是(cost,val),一个物品之后也仅有两个状态,无需那么多的空间,时间。可用队列进行模拟01背包即可。虽说状态不是很多,但是50个物品,最后也可以达到2^50个状态。所以第一次用队列模拟之后结果是MLE。产生的结点还是过多。

便想到剪枝,用优先队列,按金钱递减排序,以及花费时间递增排序。我们发现有些状态是没有用的,比如说(5,5)即花费时间5,得到金钱5,以及状态(5,4)花费时间5,得到金钱4,后者明显不如前者,则后者必然可以舍弃。也就是如果金钱少但是时间多,这样的状态可以舍弃。

在队列实现中只需要两个队列,表示原来有的状态,和得到的新状态,相当于滚动数组。得到的新状态就是原来的两倍,每一个怪杀或者不杀,都要保存。然后根据优先队列进行优化。

再一次膜拜下ZeroClock神牛,我无耻的刷到了0ms。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define inf 1<<29
using namespace std;
struct monster{
	int cost,val;
}mon[55];
struct Node{
	int cost,val;
	bool operator<(const Node n1)const{
		return n1.val!=val?val<n1.val:cost>n1.cost;
	}
}s,e;
vector<monster>group[51];
int cnt,n,m,ans;
bool mat[51][51],flag[51];
void dfs(int u){
	flag[u]=true;
	group[cnt].push_back(mon[u]);
	for(int i=1;i<=n;i++)
		if(!flag[i]&&mat[u][i])
			dfs(i);
}
void divid_group(){
	cnt=0;
	memset(flag,false,sizeof(flag));
	for(int i=1;i<=n;i++)
		if(!flag[i]){
			cnt++;
			group[cnt].clear();
			dfs(i);
		}
}
void slove(){
	ans=inf;
	priority_queue<Node>que1,que2;
	for(int i=1;i<=cnt;i++){
		while(!que1.empty()) que1.pop();
		while(!que2.empty()) que2.pop();
		s.cost=s.val=0;
		que1.push(s);
		for(int j=0;j<group[i].size();j++){
			while(!que1.empty()){
				s=que1.top();
				que1.pop();
				que2.push(s);
				s.cost+=group[i][j].cost;
				s.val+=group[i][j].val;	
				if(s.val>=m){
					ans=min(ans,s.cost);
					continue;
				}
				if(s.cost>=ans)
					continue;
				que2.push(s);
			}
			int mincost=inf;
			while(!que2.empty()){
				s=que2.top();
				que2.pop();
				if(s.cost<mincost)
		    		que1.push(s),mincost=s.cost;
			}
		}
	}
}
void scanf_(int &num){ 
	char in;      
	while((in=getchar())>'9'||in<'0');  
	num=in-'0';      
	while(in=getchar(),in>='0'&&in<='9')    
		num*=10,num+=in-'0';
} 
void printf_(int num){     
	int ans[10],top=0;   
	while(num!=0){   
		ans[top++]=num%10;   
		num/=10;   
	}    
	if(top==0)     
		putchar('0');  
	for(int i=top-1;i>=0;i--){  
		char ch=ans[i]+'0';     
		putchar(ch);    
	}
} 
int main(){
	int t,cas=0;
	scanf_(t);
	while(t--){
		scanf_(n);scanf_(m);
		memset(mat,false,sizeof(mat));
		for(int i=1;i<=n;i++){
			int k,u;
			scanf_(mon[i].cost);scanf_(mon[i].val);scanf_(k);
			while(k--){
				scanf_(u);
				mat[i][u]=true;
			}
		}
		divid_group();
		slove();
		printf("Case %d: ",++cas);
		if(ans==inf)
			puts("Poor Magina, you can't save the world all the time!");
		else{
			printf_(ans);
			puts("");
		}
	}
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics