HDU 2059 龜兔賽跑
Problem Description
據說在很久很久以前，可憐的兔子經曆了人生中最大的打擊——賽跑輸給烏龜後，心中郁悶，發誓要報仇雪恨，于是躲進了杭州下沙某農業園卧薪嘗膽潛心修煉，終于練成了絕技，能夠毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找機會好好得教訓一下烏龜，以雪前恥。
最近正值HDU舉辦50周年校慶，社會各大名流齊聚下沙，兔子也趁此機會向烏龜發起挑戰。雖然烏龜深知獲勝希望不大，不過迫于輿論壓力，隻能接受挑戰。
比賽是設在一條筆直的道路上，長度為L米，規則很簡單，誰先到達終點誰就算獲勝。
無奈烏龜自從上次獲勝以後，成了名龜，被一些八卦雜志稱為“動物界的劉翔”，廣告不斷，手頭也有了不少積蓄。為了能夠再赢兔子，烏龜不惜花下血本買了最先進的武器——“”小飛鴿”牌電動車。這輛車在有電的情況下能夠以VT1 m/s的速度“飛馳”，可惜電池容量有限，每次充滿電最多隻能行駛C米的距離，以後就隻能用腳來蹬了，烏龜用腳蹬時的速度為VT2 m/s。更過分的是，烏龜竟然在跑道上修建了很多很多（N個)的供電站，供自己給電動車充電。其中，每次充電需要花費T秒鐘的時間。當然，烏龜經過一個充電站的時候可以選擇去或不去充電。
比賽馬上開始了，兔子和帶着充滿電的電動車的烏龜并列站在起跑線上。你的任務就是寫個程式，判斷烏龜用最佳的方案進軍時，能不能赢了一直以恒定速度奔跑的兔子。
Input
本題目包含多組測試，請處理到檔案結束。每個測試包括四行：
第一行是一個整數L代表跑道的總長度
第二行包含三個整數N，C，T，分别表示充電站的個數，電動車沖滿電以後能行駛的距離以及每次充電所需要的時間
第三行也是三個整數VR，VT1，VT2，分别表示兔子跑步的速度，烏龜開電動車的速度，烏龜腳蹬電動車的速度
。。。。。
Output
當烏龜有可能赢的時候輸出一行 “What a pity rabbit!”。否則輸出一行”Good job,rabbit!”;
題目資料保證不會出現烏龜和兔子同時到達的情況。
Sample Input
100
3 20 5
5 8 2
10 40 60
100
3 60 5
5 8 2
10 40 60
Sample Output
Good job,rabbit!
What a pity rabbit!
這道題也是不錯，一開始想一步一步來，但是這是不一定的，前一步的最優解并不一定是下一步的依據，其中有剩餘電量，充不充之類的雲雲，但是要動歸又不知道怎麼歸。。。。 也是參考了别人的。。。 這樣是不對的。。
應該是這個點i他前面的點 從0到 它之前即i-1 的dp值以及從這些點充滿電到這點時間的和的最小值。至于為什麼每個都假設充滿電呢，因為對一個點有兩種情況，有剩餘電量繼續走不沖，或是沖了再走，但是對于第一種情況，可以認為，他之前點（如i-4~i的轉移）的資料已經把他不沖給包括進去了，是以再考慮的話就重複了，就是這樣。
應該先找到動态規劃的對象，再根據特性來簡化公式，學習了。注意細節，double啊，第一個0點不用T之類的。
代碼
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[];
double dp[];
int main()
{
int L;
while(scanf("%d",&L)!=EOF)
{
int N,C,T;
int VR,VT1,VT2;
scanf("%d %d %d",&N,&C,&T);
scanf("%d %d %d",&VR,&VT1,&VT2);
memset(a,,sizeof(a));
memset(dp,,sizeof(dp));
for(int i=; i<=N; i++)
scanf("%d",&a[i]);
a[N+]=L;
double temp;
for(int i=; i<=N+; i++)
{
double min1=;
for(int j=; j<i; j++)
{
int k=a[i]-a[j];
if(k<C)
temp=k*/VT1;
else
temp=(k-C)*/VT2+C*/VT1;
if(j!=)
temp+=T;
if(min1>dp[j]+temp)
min1=dp[j]+temp;
}
dp[i]=min1;
}
printf(dp[N+]>(L*/VR)?"Good job,rabbit!\n":"What a pity rabbit!\n");
}
return ;
}