題目連結:
給定一正整數 n ( n ≦ 30 ),代表有 n 個里程點。這n個里程點的位置介於 1 ~ 10, 000 之間,且由小到大排序。
現在從位置 0 出發(算做第 0 個里程點),每一天只能走固定距離 200 。太少、太多都會被懲罰,懲罰成本為(200 - 實際走的距離)^ 2。而一次只能在兩個里程點之間移動,不能停在兩里程點的中途。
求走到最後一個里程點,得到的最小可能之懲罰成本,並輸出走的路徑(各里程點)。
當 n = 0 時,程式結束。
4
190 260 385 540
5
130 180 230 330 450
0
因為 n 的值不大,所以用一般的 DP (動態規劃)的想法來做即可。
首先,我們把走到每個里程點的成本設為極大的值,以便後續處理。而現在我們以
4
190 260 385 540
這組數據為例:
先看第一個里程點:
190 260 385 540
因為是第一個,前面沒有任何里程點。因此走到這裡的成本為(200 - 190)^ 2 = 100。
可以看出,如果從第一個里程點到這裡,總成本為 100 + (200 - (260 - 190))^ 2 = 17000,比從起點直接過來的成本(3600)還高。所以走到這邊的最佳路徑為:0 2
再來是第三個里程點:
190 260 385 540
從起點過來的成本是 34225 ,從第二個里程點過來為 9225 ,都大過從第一點過來。
因此,到這點的最佳路徑為:0 1 3 ,成本為 125 。
最後是第四個里程點:
190 260 385 540
同上,最佳的走法是:0 1 3 4,總成本為 2150 。
因此,走到最後一個里程點的走法 0 1 3 4 ,即是所求。其他測試資料也是同理:到某一里程點,跟前面的最佳走法做結合。取成本最小的,即是從起點到此點的作家走法。以此算法算到最後一個點中途的經過的路徑即為題目要求之答案。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。