首页 > 代码库 > hdu 2059 龟兔赛跑 (dp)
hdu 2059 龟兔赛跑 (dp)
/* 把起点和终点比作加油站,那总共有n+2个加油站了, 每次都求出从第0个到第j个加油站(j<i)分别在加满油的情况下到第i个加油站的最短时间dp[i], 最终的dp[n+1]就是最优解了。 */ # include <stdio.h> # include <algorithm> # include <string.h> # define INF 999999999; using namespace std; int main() { int L,n,c,t,i,j; double min1,tmp; int vr,vt1,vt2; int path[100010]; double dp[100010]; while(~scanf("%d%d%d%d",&L,&n,&c,&t)) { scanf("%d%d%d",&vr,&vt1,&vt2); path[0]=0; for(i=1; i<=n; i++) scanf("%d",&path[i]); path[n+1]=L; dp[0]=0; for(i=1; i<=n+1; i++) { dp[i]=INF; for(j=0; j<i; j++) { int ll=path[i]-path[j]; if(c>=ll) tmp=ll*1.0/vt1; else tmp=c*1.0/vt1+(ll-c)*1.0/vt2; if(j!=0) tmp+=t; if(dp[i]>dp[j]+tmp) dp[i]=dp[j]+tmp; } } if(dp[n+1]>L*1.0/vr) printf("Good job,rabbit!\n"); else printf("What a pity rabbit!\n"); } return 0; }
hdu 2059 龟兔赛跑 (dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。