[acm]HDOJ 2059 龟兔赛跑

 1 //11512698    2014-08-21 17:11:55    Accepted    2059    
 2 //62MS    368K    969 B    G++    空信高手
 3 //起点和终点，共n+2个点，n+2个状态，简单DP即可
 4 #include<iostream>
 5 #include<cstdio>
 6 using namespace std;
 7 const int MAX=150;
 8 const double INF=0xfffff;
 9 double DP[MAX];
10 int s[MAX];
11 using namespace std;
12 double min(double t1,double t2)
13 {
14     return (t1<t2)?t1:t2;
15 }
16 int main()
17 {
18     freopen("input.txt","r",stdin);
19     int L;
20     int N,C,T;
21     int VR,VT1,VT2;
22     double Time;
23     while(cin>>L)
24     {
25         cin>>N>>C>>T>>VR>>VT1>>VT2;
26         for(int i=1;i<=N;i++)
27             cin>>s[i];
28         s[N+1]=L;
29         s[0]=0;
30         DP[0]=0;
31         for(int i=1;i<=N+1;i++)
32         {
33             DP[i] = INF;
34             for(int j=0;j<i;j++)
35             {
36                 int dis=s[i]-s[j];
37                 if(dis>C) Time=((double)C)/VT1+((double)(dis-C))/VT2;
38                 else Time=((double)dis)/VT1;
39                 Time+=DP[j];
40                 if(j>0)
41                     Time += T;
42                 DP[i]=min(DP[i],Time);
43             }
44         }
45         if(DP[N+1]<((double)L/VR))
46             cout<<"What a pity rabbit!"<<endl;
47         else
48             cout<<"Good job,rabbit!"<<endl;
49     }
50     return 0;
51 }