uva-1025 - A Spy in the Metro

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466

解題策略

動態規劃

dp[T][N] 在T時間到第N站的總等待時間，在車站dp[i][j]有三種動作：

(1)停留在原車站1單位時間：dp[i][j] = dp[i+1][j]+1;

(2)搭上車子往右往下一個車站，如果有車可以搭，且未到終點站N，時間沒有超過T：

if (train1[i][j] && j<N && (i+t[j])<=T) dp[i][j] = min(dp[i][j],dp[i+t[j]][j+1]);

//dp[i][j]與dp[i+t[j]][j+1]有相同等待時間

(3)搭上車子往左往上一個車站，如果有車子，且未到起站1，時間沒有超過T：

if (train2[i][j] && j>1 && (i+t[j-1])<=T) dp[i][j] = min(dp[i][j],dp[i+t[j-1]][j-1]);

//dp[i][j]與dp[i+t[j-1]][j-1]有相同等待時間

dp初始值，每一個元素都設定成一個很大的數值，dp[T][N]=0。

結果為dp[0][1]，時間0車站1的總等待時間