有一台切割棍子的機器，每次將一段棍子會送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度 $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] \sim p[N]$，數字間以空白隔開，座標的標示的方式是以棍子左端為 $0$，而右端為 $L$。
$N \le 200$， $L \le 10^6$。
最小的切割總成本。
3 10 2 4 7
20
5 10 1 6 7 8 9
24
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||