首页 > 代码库 > hdu2059 龟兔赛跑 DP
hdu2059 龟兔赛跑 DP
N^2的dp,刚入门的时候很难想到,dp[i]表示到达第i个点的最小时间,可以从之前任意一点处加上充电时间充电转移过来。
1 #include<stdio.h> 2 #define min(a,b) (a)<(b)?a:b 3 int L,N,C,T,VR,VT1,VT2,p[102]; 4 double f(int d) 5 { 6 if(d<=C) return (double)d/VT1+T; 7 else return (double)C/VT1+(double)(d-C)/VT2+T; 8 } 9 int main(){ 10 while(scanf("%d%d%d%d%d%d%d",&L,&N,&C,&T,&VR,&VT1,&VT2)!=EOF){ 11 double tr=(double)L/VR,ans[102]; 12 int i,j; 13 for(i=1;i<=N;i++)scanf("%d",&p[i]); 14 p[N+1]=L; 15 for(i=1;i<=N+1;i++){ 16 ans[i]=f(p[i])-T; 17 for(j=1;j<i;j++) ans[i]=min(ans[i],(ans[j]+f(p[i]-p[j]))); 18 } 19 if(ans[N+1]<tr) printf("What a pity rabbit!\n"); 20 else printf("Good job,rabbit!\n"); 21 } 22 return 0; 23 }
hdu2059 龟兔赛跑 DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。