龟兔赛跑
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4683 Accepted Submission(s): 1771
Problem Description
据说在很久很久以前,可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后,心中郁闷,发誓要报仇雪恨,于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼,终于练成了绝技,能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟,以雪前耻。
最近正值HDU举办50周年校庆,社会各大名流齐聚下沙,兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大,不过迫于舆论压力,只能接受挑战。
比赛是设在一条笔直的道路上,长度为L米,规则很简单,谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后,成了名龟,被一些八卦杂志称为“动物界的刘翔”,广告不断,手头也有了不少积蓄。为了能够再赢兔子,乌龟不惜花下血本买了最先进的武器——“"小飞鸽"牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”,可惜电池容量有限,每次充满电最多只能行驶C米的距离,以后就只能用脚来蹬了,乌龟用脚蹬时的速度为VT2 m/s。更过分的是,乌龟竟然在跑道上修建了很多很多(N个)的供电站,供自己给电动车充电。其中,每次充电需要花费T秒钟的时间。当然,乌龟经过一个充电站的时候可以选择去或不去充电。
比赛马上开始了,兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序,判断乌龟用最佳的方案进军时,能不能赢了一直以恒定速度奔跑的兔子。
Input
本题目包含多组测试,请处理到文件结束。每个测试包括四行:
第一行是一个整数L代表跑道的总长度
第二行包含三个整数N,C,T,分别表示充电站的个数,电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数VR,VT1,VT2,分别表示兔子跑步的速度,乌龟开电动车的速度,乌龟脚蹬电动车的速度
第四行包含了N(N<=100)个整数p1,p2...pn,分别表示各个充电站离跑道起点的距离,其中0<p1<p2<...<pn<L
其中每个数都在32位整型范围之内。
Output
当乌龟有可能赢的时候输出一行 “What a pity rabbit!"。否则输出一行"Good job,rabbit!";
题目数据保证不会出现乌龟和兔子同时到达的情况。
Sample Input
100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60
Sample Output
Good job,rabbit!
What a pity rabbit!
这是一道DP问题,开始我想的状态是在加油站 加油 或不加油两种状态,而dp也只考虑前一个状态,取当前状态的最小值,加上以前所有的状态,而简单测试也过了,但提交后wa,看了网上的解题报告,才知道不是仅仅考虑上一个状态,而是考虑前面的所有状态:
Ac代码:
错误代码:
#include <iostream>
using namespace std;
const int MAX = 110;
int N;
double dp[MAX][2]; //二维数组的dp[i][0]存0 ~i加油站的最小时间,dp[i][1]存上一状态乌龟还可以骑车多少距离
double L, C, T, VR, VT1, VT2;
double p[MAX];
int main()
{
int i;
double len, a, b, temp;
while(cin>>L)
{
cin>>N>>C>>T;
cin>>VR>>VT1>>VT2;
for(i = 1; i <= N; i++)
cin>>p[i];
p[0] = 0.0;
p[N + 1] = L;
memset(dp, 0.0, sizeof(dp));
for(i = 1; i <= N + 1; i++)
{
len = p[i] - p[i - 1];
if(i == 1)
{
dp[i][0] = len >= C ? C / VT1 + (len - C) / VT2 : len / VT1;
if(C > len)
dp[i][1] = C - len;
}else
{
a = len >= C ? T + C / VT1 + (len - C) / VT2 : len / VT1 + T;
if(C > len)
temp = C - len;
if(dp[i - 1][1])
{
b = len >= dp[i - 1][1] ? dp[i - 1][1] / VT1 + (len - dp[i - 1][1]) / VT2
:len / VT1;
if(dp[i - 1][1] > len)
dp[i][1] = len - dp[i - 1][1];
}
else
b = len / VT2;
dp[i][0] = a > b ? b : a;
if(a < b)
dp[i][1] = temp;
dp[i][0] += dp[i - 1][0];
}
}
cout<<dp[N + 1][0]<<endl;
if(dp[N + 1][0] < L / VR)
cout<<"What a pity rabbit!\n";
else
cout<<"Good job,rabbit!\n";
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
HDU的一题........HDU DP动态规
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码
hdu动态规划算法集锦
hdu 1166线段树代码
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu题目分类
HDU图论题目分类