DP 問題的關(guān)鍵在于：如何分解子問題以及求得子問題的最優(yōu)解
//這題可以看成0,1...n,n+1一共n+2個(gè)終點(diǎn)站包括起始點(diǎn),分別求出到達(dá)每個(gè)站的最短時(shí)間即可
//第 i 站時(shí)用前面的timeT[i - 1] + 后面的可能解，由于timeT保存的是到該站時(shí)的最短時(shí)間，所以不斷遞歸 i 之至 n 就可以求得最優(yōu)解
//dp[i]=dp[i-1]+f(i-1,i)(即i-1,到i的最短時(shí)間)
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int L;
int N, C, T;
int vr, vt1, vt2;
int p[103]; //記錄各站p[i]到起點(diǎn)的距離
double timeT[103]; //記錄第i段的最短時(shí)間
double timeR;
while ( scanf ("%d",&L) != EOF )
{
scanf ("%d%d%d", &N , &C, &T);
scanf ("%d%d%d", &vr, &vt1, &vt2);
//兔子的時(shí)間
timeR = L * 1.0 / vr;
//記錄各站p[i]到起點(diǎn)的距離
p[0] = 0;
p[N + 1] = L;
for (int i = 1; i <= N; i ++)
{
scanf ("%d", &p[i]);
}
//找到p[i] 到 p[i + 1]段的最短耗時(shí)
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
雪黛依夢(mèng) 閱讀(272)
評(píng)論(0) 編輯 收藏 引用