切棍子 (AP325 P-6-17)

有一台切割棍子的機器，每次將一段棍子送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度 \(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\)。
• 切割點兩兩不同，且 \(0 < p[i] < L\)。

輸出格式

輸出最小的切割總成本。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

3 10
2 4 7

範例輸出 1

20

範例輸入 2

5 10
1 6 7 8 9

範例輸出 2

24

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 P-6-17，第 197 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。