首页 > 代码库 > [acm]HDOJ 2059 龟兔赛跑
[acm]HDOJ 2059 龟兔赛跑
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2059
起点和终点,共n+2个点,n+2个状态,简单DP即可。
1 //11512698 2014-08-21 17:11:55 Accepted 2059 2 //62MS 368K 969 B G++ 空信高手 3 //起点和终点,共n+2个点,n+2个状态,简单DP即可 4 #include<iostream> 5 #include<cstdio> 6 using namespace std; 7 const int MAX=150; 8 const double INF=0xfffff; 9 double DP[MAX];10 int s[MAX];11 using namespace std;12 double min(double t1,double t2)13 {14 return (t1<t2)?t1:t2;15 }16 int main()17 {18 freopen("input.txt","r",stdin);19 int L;20 int N,C,T;21 int VR,VT1,VT2;22 double Time;23 while(cin>>L)24 {25 cin>>N>>C>>T>>VR>>VT1>>VT2;26 for(int i=1;i<=N;i++)27 cin>>s[i];28 s[N+1]=L;29 s[0]=0;30 DP[0]=0;31 for(int i=1;i<=N+1;i++)32 {33 DP[i] = INF;34 for(int j=0;j<i;j++)35 {36 int dis=s[i]-s[j];37 if(dis>C) Time=((double)C)/VT1+((double)(dis-C))/VT2;38 else Time=((double)dis)/VT1;39 Time+=DP[j];40 if(j>0)41 Time += T;42 DP[i]=min(DP[i],Time);43 }44 }45 if(DP[N+1]<((double)L/VR))46 cout<<"What a pity rabbit!"<<endl;47 else48 cout<<"Good job,rabbit!"<<endl;49 }50 return 0;51 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。