原题链接,于是决定斟酌差异兔子和海龟的赛跑

基础演练 龟兔赛跑预测  

原题链接

日子范围:1.0s   内部存款和储蓄器限制:51二.0MB

描述

遗闻在很久很久在此以前,可怜的兔子经历了人生中最大的打击——赛跑输给水龟后,心中苦闷,发誓要报仇雪耻,于是躲进了维尔纽斯下沙某农业园低头折节潜心修炼,终于练成了才有所长,能够毫不安歇能够牢固的速度(V普拉多m/s)一贯跑。兔子一直想找机会能够得教训一下乌龟,以雪前耻。
目前正值HDU举行50周年校庆,社会各大球星齐聚下沙,兔子也趁此机会向海龟发起挑衅。固然水龟深知获胜希望非常的小,然而迫于舆论压力,只好接受挑战。
竞技是设在一条笔直的道路上,长度为L米,规则很简短,何人先到达极限什么人固然获胜。
迫不得已陆龟自从上次制服之后,成了名龟,被部分八卦杂志称为“动物界的刘翔先生”,广告不断,手头也有了广大存款。为了能够再赢兔子,水龟不惜花下血本买了起首进的军械——“”小飞鸽”牌电高铁。那辆车在有电的场馆下能够以VT一m/s的进程“飞驰”,可惜电池容积有限,每一次充满电最六只可以行驶C米的偏离,未来就只好用脚来蹬了,乌龟用脚蹬时的进程为VT贰m/s。更过分的是,水龟竟然在跑道上修建了过多居多(N个)的供发电站,供自身给电轻轨充电。个中,每回充电必要费用T分钟的日子。当然,海龟经过1个充发电站的时候能够挑选去或不去充电。
竞赛立刻起初了,兔子和带着充满电的电高铁的海龟并列站在起跑线上。你的天职就是写个程序,判定乌龟用一流的方案进军时,能否赢了向来以一直速度奔跑的兔子。

      

输入

本标题包蕴多组测试,请管理到文件甘休。每个测试包罗四行:
首先行是二个整数L代表跑道的总秘书长度
其次行蕴涵八个整数N,C,T,分别代表充发电站的个数,电轻轨冲满电以往能行驶的离开以及历次充电所必要的小运
其3行也是两个整数VCR-V,VT壹,VT2,分别代表兔子跑步的速度,乌龟开电高铁的快慢,乌龟脚蹬电火车的快慢
第五行包括了N(N<=十0)个整数p1,p二…pn,分别代表各类充发电站离跑道源点的离开,在那之中0<p1<p二<…<pn<L
中间每种数都在三九位整型范围以内。

锦囊1

输出

当海龟有非常的大可能赢的时候输出1行 “What a pity rabbit!”。不然输出壹行”Good
job,rabbit!”;
标题数据保险不会并发乌龟和兔子同时到达的气象。

  模拟。

样例输入

100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60

 

样例输出

Good job,rabbit!
What a pity rabbit!

主题材料讲述

思路

刚开端没仔细想,笔者感到是名缰利锁,然后WA了两发才清醒,原来是DP。
知晓为什么贪心不得法后,仔细思忖很轻松得出状态转移方程dp[i] =
min{dp[i], dp[j] + time(p[i] – p[j]) + t}

dp数组表示到第i个充发电站的光阴,time为跑那段距离所要求的时光,t是充电时间。j枚举0到i-1的每个点,算出最小值。
唯独那里供给考虑j=0,即先导的时候是不须求充电时间的,所以给dp数组赋初值的时候能够赋值为从起源直接到i处的时日。

  话说那一个世界上有多姿多彩的兔子和乌龟,不过钻探发掘,全体的兔子和乌龟都有多个体协会同的风味——喜欢赛跑。于是世界上家家户户角落都持续在发出着乌龟和兔子的比赛,小华对此很感兴趣,于是决定研究分化兔子和海龟的赛跑。他发掘,兔子就算跑比水龟快,但它们有强烈的疾病——骄傲且懒惰,于是在与海龟的竞技前,1旦任1秒停止后兔子开采自个儿抢先t米或上述,它们就会停下来安息s秒。对于差别的兔子,t,s的数值是见仁见智的,不过全体的幼龟却是一致——它们不到顶点决不结束。
  然则有点竞赛非凡久远,全程观看会消耗大批量时刻,而小华开采只要在每场竞赛伊始后记录下兔子和乌龟的数据——兔子的快慢v一(表示每秒兔子能跑v1米),乌龟的进程v二,以及兔子对应的t,s值,以及赛道的长度l——就能预测出竞赛的结果。可是小华很懒,不想经过手工业计算估量出比赛的结果,于是她找到了你——清华Computer系的高才生——请求增派,请您写2个程序,对于输入的一场比赛的数量v一,v2,t,s,l,预测这场竞赛的结果。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, c, t;
int vr, vt1, vt2;

double time(int s)
{
    if(c >= s) return 1.0 * s / vt1;
    return 1.0 * c / vt1 + 1.0 * (s - c) / vt2;
}

int main()
{
    int l;
    while(~scanf("%d", &l))
    {
        scanf("%d %d %d", &n, &c, &t);
        scanf("%d %d %d", &vr, &vt1, &vt2);
        int p[102] = {0}; p[n+1] = l;
        double aim = 1.0 * l / vr;
        for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
        double dp[102]; dp[0] = 0;
        for(int i = 1; i <= n + 1; i++)
        {
            dp[i] = time(p[i]);
            for(int j = 1; j < i; j++)
                dp[i] = min(dp[j] + t + time(p[i] - p[j]), dp[i]);
        }
        if(aim > dp[n+1]) printf("What a pity rabbit!\n");
        else printf("Good job,rabbit!\n");
    }
    return 0;
}

输入格式

  输入唯有1行,包括用空格隔断的多少个正整数v一,v二,t,s,l,当中(v一,v二<=100;t<=300;s<=拾;l<=一千0且为v一,v2的翻番)

出口格式

  输出包罗两行,第一行输出比赛结果——1个大写字母“T”或“奇骏”或“D”,分别表示乌龟获胜,兔子获胜,可能两者同时到达极限。
  第壹行输出二个正整数,表示胜球者(或许双方同时)到达顶峰所费用的日子(秒数)。

样例输入

10 5 5 2 20

样例输出

D
4

样例输入

10 5 5 1 20

样例输出

R
3

样例输入

10 5 5 3 20

样例输出

T
4

 

作者注释:题目废话繁多,内轻巧懂。

只顾一下几点:

一:兔子初叶睡觉的临界条件;

贰:兔子截止睡觉的逼近条件;

3:兔子睡觉时,海龟前进的离开总计:

while(ss--!=0 && gui<l){//若兔子还没有睡醒且乌龟没有到终点时执行 
  gui=gui+vg;//兔子睡觉s秒乌龟跑的距离为vg*s,每while循环一次过了1秒 
  time++;//比赛时间在增加 
}continue;//结束此次循环进行下一次循环

留意第二行不用乘以时间,因为每while循环3次表过了一秒。

四:兔子醒了后,即时跳出循环,使用continue;//甘休此次巡回实行下叁回巡回

代码如下:

 1 /*
 2     T--乌龟获胜
 3     R--兔子获胜
 4     D--两者同时到达终点
 5 */
 6 #include<stdio.h>
 7 main(){
 8     int vt,vg,t,s,l;
 9     scanf("%d%d%d%d%d",&vt,&vg,&t,&s,&l);
10     int tu=0,gui=0;//龟兔跑的路程
11     int time=0;//用的时间 
12     int ss;//用来记录兔子睡觉的时间 
13     while(tu<l && gui<l){//均没有到终点时执行循环 
14         if(tu-gui>=t){//若兔子超过乌龟t米,开始睡觉 
15             ss=s;
16             while(ss--!=0 && gui<l){//若兔子还没有睡醒且乌龟没有到终点时执行 
17                 gui=gui+vg;//兔子睡觉s秒乌龟跑的距离为vg*s,每while循环一次过了1秒 
18                 time++;//比赛时间在增加 
19             }continue;//结束此次循环进行下一次循环
20         }
21         gui=gui+vg*1;//乌龟跑的距离 
22         tu=tu+vt*1;//兔子跑的距离
23         time++;//比赛时间在增加
24     }
25     
26     if(tu>=l && gui>=l)
27         printf("D\n");
28     else if(tu>=l && gui<l)
29         printf("R\n");
30     else
31         printf("T\n");
32     printf("%d",time);
33 }