首页 > 代码库 > [acm]HDOJ 2059 龟兔赛跑

[acm]HDOJ 2059 龟兔赛跑

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2059

起点和终点,共n+2个点,n+2个状态,简单DP即可。


 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         else48             cout<<"Good job,rabbit!"<<endl;49     }50     return 0;51 }