http://acm.hdu.edu.cn/showproblem.php?pid=2059
DP 入门题
/*
与第2037题一样的算法。
我们把起点和终点,以及中间的n个充电站看做n+2个点。
这里长度为n+2的数组里保存的到达该站点所需时间的最优解。
自然,D[0](起点)的值就是0。
然后依次往下规划。
到了第i点后,就让j从0循环到i-1,依次代表从j站充满了电一直开到i站,这样得到到达i站所需要的最短时间。
最后比较到达第n+2站(终点)的时间与兔子所花的时间就可以了。
*/
#include <iostream>
#include <limits.h>
using namespace std;
double time[102];
int d[102];
int main()
{
int L,N,C,T,VR,V1,V2;
int len;
int i,j;
double min, min_t;
while (scanf("%d",&L)!=EOF) {
scanf("%d%d%d",&N,&C,&T);
scanf("%d%d%d",&VR,&V1,&V2);
time[0] = d[0] = 0;
for (i = 1; i <= N; i++)
scanf("%d", &d[i]);
d[i] = L;
for (i = 1; i < N+2; i++)
{
min = 0xffffff;
for (j = 0; j < i; j++)
{
len = d[i] - d[j];
min_t = time[j] + ( len>C ? 1.0*C/V1+1.0*(len-C)/V2 : 1.0*len/V1 );
if (j) min_t += T;
if (min > min_t) min = min_t;
}
time[i] = min;
}
puts(1.0*L/VR > time[N+1] ? "What a pity rabbit!":"Good job,rabbit!");
}
return 0;
}