DP 问题的关键在于：如何分解子问题以及求得子问题的最优解
//这题可以看成0,1...n,n+1一共n+2个终点站包括起始点,分别求出到达每个站的最短时间即可
//第 i 站时用前面的timeT[i - 1] + 后面的可能解，由于timeT保存的是到该站时的最短时间，所以不断递归 i 之至 n 就可以求得最优解
//dp[i]=dp[i-1]+f(i-1,i)(即i-1,到i的最短时间)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int L;
int N, C, T;
int vr, vt1, vt2;
int p[103]; //记录各站p[i]到起点的距离
double timeT[103]; //记录第i段的最短时间
double timeR;
while ( scanf ("%d",&L) != EOF )
{
scanf ("%d%d%d", &N , &C, &T);
scanf ("%d%d%d", &vr, &vt1, &vt2);
//兔子的时间
timeR = L * 1.0 / vr;
//记录各站p[i]到起点的距离
p[0] = 0;
p[N + 1] = L;
for (int i = 1; i <= N; i ++)
{
scanf ("%d", &p[i]);
}
//找到p[i] 到 p[i + 1]段的最短耗时
timeT[0] = 0; //递归出口
double len;
double e, min;
for (int i = 1; i <= N + 1; i ++)
{
min = 9999999.9;
for (int j = 0; j < i; j ++)
{
len = p[i] - p[j];
if (len > C)
e = ( 1.0 * C / vt1 ) + (len - C + 0.0) * 1.0 / vt2 ;
else
e = len * 1.0 / vt1 ;
e += timeT[j];
if (j)
e += T;
if ( e < min)
min = e;
}
timeT[i] = min;
}
if (timeT[N + 1] < timeR)
{
printf ("What a pity rabbit!\n");
}
else
printf ("Good job,rabbit!\n");
}
return 0;
}
posted on 2010-08-15 16:16
雪黛依梦 阅读(257)
评论(0) 编辑 收藏 引用