首页 > 代码库 > hdu 2059 龟兔赛跑(DP)
hdu 2059 龟兔赛跑(DP)
题目意思:
http://acm.hdu.edu.cn/showproblem.php?pid=2059
题目没有说明白的是,不能用电动车剩余的能力,每次都要充满。
题目分析:
动态规划问题,可以对站点进行DP,加上起点和终点一共有n+2个站,起点表示站点0,dp[n+1]就是乌龟的最优时间,即最短时间,那么动态转化方程为:dp[i]=min(dp[i],dp[j]+t1); t1:从j到i的最优(最少)时间。
AC代码:
/** *@xiaoran *DP,题意不清楚,不能用上次剩下的能量 *dp[i]=min(dp[i],dp[j]+cost),cost:从j——>i的时间 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; const double DOB_MAX=1000000.0; int path[110]; double dp[110]; int main() { int l,n,c,t,vr,vt1,vt2; while(scanf("%d",&l)==1){ scanf("%d%d%d",&n,&c,&t); scanf("%d%d%d",&vr,&vt1,&vt2); for(int i=1;i<=n;i++){ scanf("%d",&path[i]); } path[n+1]=l; dp[0]=0; double t1,t2; for(int i=1;i<=n+1;i++){ dp[i]=DOB_MAX; for(int j=0;j<i;j++){//从j~i站点的最优策略 int len=path[i]-path[j]; //1、加油 if(c>=len) t1=len*1.0/vt1;//全程电动车 else t1=c*1.0/vt1+(len-c)*1.0/vt2;//用电动车走c,剩下的脚蹬 if(j) t1+=t;//算上加油的时间 //2、不加油 t2=len*1.0/vt2; t1=min(t1,t2);//从i到j的最小花费 dp[i]=min(dp[i],dp[j]+t1); } } if(dp[n+1]<l*1.0/vr) printf("What a pity rabbit!\n"); else printf("Good job,rabbit!\n"); } return 0; }
hdu 2059 龟兔赛跑(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。