d079: P-6-17. 切棍子
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

有一台切割棍子的機器,每次將一段棍子會送入此台機器時,我們可以選擇棍子上的

切割位置,機器會將此棍子在指定位置切斷,而切割成本是該段棍子的長度。現在有

一根長度 L 的棍子,上面標有 n 個需要切割的位置座標,因為不同的切割順序會影響

切割總成本,請計算出最小的切割總成本。

例如 L=10,三個切割點的座標是(2,4,7)。如果切割順序是(2,4,7),則第一次切

的成本是 10,第二次的成本是 8,第三次成本 6,總成本 10+8+6=24。如果切割順

序改成(4,2,7),第一次切的成本是 10,切成長度 4 與 6 的兩段,第二次的成本是

4,第三次成本 6,總成本 10+4+6=20。

Input

第一行有兩個正整數 n 與 L。第二行有 n 個正整數,依序代表由小到大的

切割點座標 p[1]~p[N],數字間以空白隔開,座標的標示的方式是以棍子左端為 0,

而右端為 L。N <= 200,L <= 1e6。

Output

:最小的切割總成本。

Sample Input
// 1
3 10
2 4 7
// 2
5 10
1 6 7 8 9
Sample Output
// 1
20
// 2
24
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」