2046 : 生化危机
时间限制:1 Sec内存限制:128 MiB
提交:19答案正确:8
题目描述
当致命的T病毒从Umbrella Corporation 逃出的时候，地球上大部分的人都死去了。
麻烦的是，他们并没有真正的死去。
爱丽诗在一个狭窄的巷子中，遇见了n个丧尸（编号1-n），巷子太窄了，爱丽诗只能按顺序解决它们。
爱丽诗擅长用匕首和弓箭，当爱丽诗面临编号为i的丧尸时，匕首每次只能解决一个丧尸用时为a[i]，弓箭每次能且只能解决两个相邻的丧尸（丧尸i,和丧尸i+1），用时为b[i]。
爱丽诗看了下时间正好是20:00:00，那么爱丽诗最快能在什么时刻解决战斗呢？
输入
先输入一个正整数T(0<T<15)，代表有T组数据，对于每组数据包含三行内容
第一行输入一个正整数n，代表丧尸的个数
第二行输入n个整数，分别代表用匕首解第i个丧尸决所花费的时间（单位为秒）
第三行输入n-1个整数，分别代表用弓箭同时解决第i个和第i+1个丧尸所用的时间（单位为秒）。
所有输入均不超过 100000
输出
对于每组数据，输出爱丽诗能够解决战斗的最早时间
样例输入
复制
1
2
1 3
4
样例输出
复制
20:00:04
提示
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> //这两个题存在惊人的相似程度, 原因其实也很简单--你想
#include<queue>
using namespace std;
int k,n,w[],a[],b[],ans[];
struct node
{
int x;
int step;
};
void bfs() ;
int main()
{
int i,T;
cin>>T;
while(T--)
{
memset(ans,,sizeof(ans));k=;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
cin>>n;
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n-;i++)
scanf("%d",&b[i]);
bfs();
sort(ans,ans+k);
int t=ans[];
int h=,m=,s=;
h=(h+t/)%;
m=(t/)%;
s=t%;
printf("%02d:%02d:%02d\n",h,m,s);
}
return ;
} void bfs() //激活下面的注释区，你将看到整个搜索的大致过程
{
memset(w,,sizeof(w));
queue<node>Q;
struct node q,p;
q.x=;q.step=;
Q.push(q);// cout<<q.x<<" "<<q.step<<" ";
while( Q.size()> )
{
p=Q.front();
Q.pop();
for(int i=;i<=;i++)
{
if(p.step>=n)
{
ans[k++]=p.x;//cout<<p.x<<" "<<p.step<<" ";
continue;
}
if(i==&&(p.step+<=n))
{
q.x=p.x+ a[p.step+];q.step=p.step+;
}
else if((i==)&&(p.step+<=n))
{
q.x=p.x+ b[p.step+];q.step=p.step+;
}
else{} // cout<<i<<" q.x: "<<q.x<<" q.step: "<<q.step<<endl;
Q.push(q); }
} return ;
}
总结：学长们说的很对，搜索是万能的！如果题目不要求时间复杂度，不要求内存，理论上任何一个题目都是可以做出来的。hdu上的那题需要更改一下，有兴趣的同学们可以试试！其实这是一道DP水题！！
【杭电的原题链接 1260:Tickets 】http://acm.hdu.edu.cn/showproblem.php?pid=1260
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring> // HDU 1260:Tickets
using namespace std;
int a[],b[],dp[],n;
int main()
{
int i,j,T,k,m;
cin>>T;
while(T--)
{
memset(a,,sizeof(a));memset(b,,sizeof(b));
memset(dp,,sizeof(dp));
cin>>n;
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n-;i++)
scanf("%d",&b[i]);
dp[]=a[];
for(i=;i<=n;i++)
{
dp[i]=min(dp[i-]+a[i],dp[i-]+b[i-]);
}
m=dp[n];
int hh=,mm=,ss=;
hh=(hh+m/)%;m=m%;
mm=m/;
ss=m%;
printf("%02d:%02d:%02d",hh,mm,ss);
if(hh<)
printf(" am\n");
else
printf(" pm\n");
} return ;
}
你懂了吧！傻眼了吧！