首页 > 代码库 > HDU 2059 龟兔赛跑
HDU 2059 龟兔赛跑
题意:中文题,不解释。
思路:将长度为L分为n+2段:0,p[1],p[2]……,p[n],L.
dp[i]为乌龟到第 i 段的最小时间,
乌龟可以再0~i-1段选择充电后到达 i 的最小时间,然后分类讨论下。
#include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath> #include<iostream> #include <queue> #include <stack> #include<algorithm> #include<set> using namespace std; #define INF 1e8 #define eps 1e-8 #define ll __int64 #define maxn 100010 #define mol 1000000007 int main() { int l,n,c,t,vr,vt1,vt2; while(~scanf("%d",&l)) { scanf("%d%d%d%d%d%d",&n,&c,&t,&vr,&vt1,&vt2); int p[105]; p[0]=0;p[n+1]=l; for(int i=1;i<=n;i++) scanf("%d",&p[i]); double dp[105]; dp[0]=0; for(int i=1;i<=n+1;i++) { double tt,minn=999999999; for(int j=0;j<i;j++) { if(p[j]+c<p[i]) { tt=c*1.0/vt1*1.0+(p[i]-p[j]-c)*1.0/vt2*1.0; } else tt=(p[i]-p[j])*1.0/vt1*1.0; if(j!=0&&dp[j]+tt+t<minn) minn=dp[j]+tt+t; else if(j==0) { minn=tt; } } dp[i]=minn; } if(l*1.0/vr*1.0>dp[n+1]) printf("What a pity rabbit!\n"); else printf("Good job,rabbit!\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。