转载请注明出处,谢谢 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;
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
hdu1001解题报告
搜索 dfs 解题代码 hdu1241
hdu 1574 passed sorce