有一台切割棍子的機器，每次將一段棍子會送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度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。
第一行有兩個正整數n與L。第二行有n個正整數，依序代表由小到大的切割點座標p[1]~p[N]，數字間以空白隔開，座標的標示的方式是以棍子左端為0，而右端為L。N ≤ 200，L ≤1e6。
最小的切割總成本。
3 10 2 4 7
20
5 10 1 6 7 8 9
24
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||