題目連結：
題目大意：
輸入有多筆測試資料。每筆第一列給定一正整數 n （1 ≦ n ≦ 40），代表有一個馬拉松依序有 n 個賽道要跑，每個賽道都有自己的得分。接著的一列給定 n 個正整數 p （10 ≦ p ≦ 100），代表每個賽道的原始分數。
現在小愛想要跑過這 n 個賽道，而在跑某個賽道的時候可以選擇加速跑過該賽道使得該賽道之得分加倍（當然可以選擇不這麼做），但是下一個賽道一定會因為要休息而跑太慢以致於無法得分（如果上一個沒加速就沒事）。
試問小愛最多可以得幾分？
範例輸入：
1
10
2
15 10
2
30 10
3
90 60 10
3
65 50 50
3
40 60 35
0
範例輸出：
20
35
60
210
230
170
解題思維：
又是一題典型的動態規劃（Dynamic Programming）之題型。
定義 Di,j ，其中 j = 0 （休息或是正常跑）或 1 （加速跑），代表著選擇策略 j 時完成第 i 個賽道可以獲得的最大分數。
可以看到如果第 i 個賽道選擇正常跑（或休息），則
Di,0 = max(Di-1,0 + Pi, Di-1,1)
其中 Pi 代表第 i 個賽道的原始分數。如果是正常跑，代表上一個賽道必不是加速跑的；如果是休息，代表上一個賽道肯定有加速跑。因此要看前一賽道哪一個策略帶來的分數較大。
而如果選擇加速跑，則
Di,1 = Di-1,0 + 2 × Pi
因為不可能連續加速跑，因此若第 i 個賽道必須加速跑，則第 i - 1 個賽道必須不能加速跑。
可以看到所求即為 max(Dn,0, Dn,1)
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
