学步园

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;
}