龟兔赛跑

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8952    Accepted Submission(s): 3444

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!

/*********************************************************************
思路看的讨论区Orz
思路：
     对于每一个充电站到底充电还是不充电,这是个问题。。。
讨论区的题解。。。
这道题目是DP中多阶段决策的典型例题
我们将起点和终点划分到N个加电站中去
这样一共有N+2点,用DP[i]表示到第i个加电站的最小耗费时间
那么在求DP[i]的时候，DP[0]...DP[i-1]已经求得
让j从0遍历到i-1,每一个j表示最后一次充电到i点
那么状态转移方程为
DP[i] = min(DP[j] + t(j, i)) //t(j, i)表示从j充完电一直到i点(中途没有充过电)

*************************************************************************/
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn = 110;
double dp[maxn]; //到达每一个加油站的最少时间
double p[maxn]; //加油站

int main()
{
    double L;
    int n; double c,t;
    double vr, vt1, vt2;
    while(scanf("%lf", &L) != EOF)
    {
        scanf("%d%lf%lf", &n,&c,&t);
        scanf("%lf%lf%lf", &vr,&vt1,&vt2);

        for(int i = 1; i <= n; i++)
            scanf("%lf", &p[i]);
        p[0] = 0; p[n+1] = L; //定义边界第 0 个加油站为起点,最后一个加油站为终点

        double RabbitTime = L/vr; //兔子用的时间

        int flag = 0;
        for(int i = 1; i <= n+1; i++) //遍历每一个加油站
        {
            dp[i] = RabbitTime+10; //初始化乌龟输了

            for(int j = 0; j < i; j++)
            {
                double len = p[i]-p[j]; //第 i 个加油站到第 j 个加油站的距离
                double time;

                if(len <= c) //直接骑车
                    time = len/vt1;
                else time = c/vt1 + (len-c)/vt2; //先把点用完,再自己踩

                if(j != 0) time += t; //加上充电时间,起点不用充电

                time += dp[j]; //加上到 j 的最短时间

                dp[i] = min(time, dp[i]); //更新到 i 的最短时间
            }
            if(dp[i] > RabbitTime) //Rabbit Win
            {
                flag = 1; break;
            }
        }

        if(flag) printf("Good job,rabbit!\n");
        else printf("What a pity rabbit!\n");
    }

    return 0;
}