切换行号显示
1 /*
2 DP
3 hdu2059 龟兔赛跑
4 ymc 2008/9/23
5 题目大意：
6 乌龟与兔子赛跑，起点为0，终点为len。
7 兔子以恒定的速度vr跑。乌龟骑着电动车。
8 电动车的速度为vt1，满电能跑c的距离，一次充电需要t的时间。
9 起始状态电动车满电，路上有n个充电点，分别距离起点p1,p2,..,pn。
10 求兔子在比赛中能否获胜。
11 分析与解题思路：
12 重点在于求解乌龟到终点的最短时间。
13 把起点和终点作为两个充电点。
14 令Time[i]为乌龟到代第i个充电点的最短时间。
15 Cap[i]为乌龟最早到代第i个充电点时电动车的最大余量。
16 Time[0]=0;Cap[0]=c;
17 则Time[i]=Min{Time[j]+Go(j,i)},0<=j<i;
18 其中Go(j,i)表示从j个充电点直接到i个充电点的最短时间，
19 如果有多个解，要求电动车余量最大。
20
21 */
22 #include <iostream>
23 #include <limits>
24 using namespace std;
25 const int N=110;
26 double p[N];
27 int n;
28 double len,c,t;
29 double vr,vt1,vt2;
30 double Time[N];
31 double Cap[N];
32 void Init()//把起点和终点看作充电点
33 {
34 scanf("%d %lf %lf",&n,&c,&t);
35 scanf("%lf %lf %lf",&vr,&vt1,&vt2);
36 p[0]=0;
37 for(int i=1;i<=n;i++)
38 scanf("%lf",&p[i]);
39 n++;
40 p[n]=len;
41 n++;
42 }
43 /*
44 从第x个充电点直接到第y个充电点，到第y个充电点时的最短时间。
45 如果时间相同，电动车余量最大。
46 */
47 void Go(int x,int y,double &tt,double &tc)
48 {
49 double t1=Time[x];
50 double t2=Time[x];
51 double c1=Cap[x];
52 double c2=Cap[x];
53 double len=p[y]-p[x];
54 //在第x个点不充电直接走
55 if(len<=c1)
56 {
57 t1+=len/vt1;
58 c1-=len;
59 }
60 else
61 {
62 t1+=c1/vt1;
63 len-=c1;
64 t1+=len/vt2;
65 c1=0;
66 }
67
68 //在第x个点充电后再走。
69 t2+=t;
70 c2=c;
71 len=p[y]-p[x];
72 if(len<=c2)
73 {
74 t2+=len/vt1;
75 c2-=len;
76 }
77 else
78 {
79 t2+=c2/vt1;
80 len-=c2;
81 c2=0;
82 t2+=len/vt2;
83 }
84 if(t1<t2||t1==t2&&c1>c2)
85 {
86 tt=t1;
87 tc=c1;
88 }
89 else
90 {
91 tt=t2;
92 tc=c2;
93 }
94 }
95
96 void DP()
97 {
98 memset(Time,0,sizeof(Time));
99 memset(Cap,0,sizeof(Cap));
100 Time[0]=0;
101 Cap[0]=c;
102 double Min,Maxc;
103 double tt,tc;
104 for(int i=1;i<n;i++)
105 {
106 Min=INT_MAX;
107 Maxc=INT_MIN;
108 for(int j=0;j<i;j++)
109 {
110 Go(j,i,tt,tc);
111 if(tt<Min||tt==Min&&tc>Maxc)
112 {
113 Min=tt;
114 Maxc=tc;
115 }
116 }
117 Time[i]=Min;
118 Cap[i]=Maxc;
119 }
120 double t1=len/vr;
121 if(t1<Time[n-1])
122 printf("Good job,rabbit!\n");
123 else
124 printf("What a pity rabbit!\n");
125 }
126
127 int main()
128 {
129 while(scanf("%lf",&len)!=EOF)
130 {
131 Init();
132 DP();
133 }
134 }