m934.
4. 合併成本
內容
有 $n$ 個數字排成一列，依序是 $a[1], a[2], a[3], \cdots, a[n]$。
每次可以挑選兩個相鄰的數字 $(u, v)$ 合併，合併會花費 $|u - v|$ 的元，合併起來的數字會變為 $u + v$。
問把 $n$ 個東西合成一個數字的最小花費是多少？
輸入說明
第一行有一個正整數 $n (1 \leq n \leq 100)$，表示有多少個東西。
第二行包含 $n$ 個整數 $a[1], a[2], a[3], \cdots, a[n]$ $(|a[i]| \leq 1000)$，相鄰兩個數字之間用空格隔開。
子題分數：
- 30%: $n \leq 13$
- 70%: 無額外限制
輸出說明
輸出最小花費。
範例輸入
#1
4 3 -1 2 5
範例輸出
#1
5
範例輸入
#2
6 -5 3 0 -4 3 -2
範例輸出
#2
18
範例輸入
#3
7 -1 -6 6 -8 7 0 -9
範例輸出
#3
36
測資資訊：
記憶體限制：
256
MB
提示 ：
範例 1 說明：
- 輸入陣列
[3, -1, 2, 5] - 合併 1 和 2：
[2, 2, 5]，花費為abs(3 - (-1)) = 4 - 合併 1 和 2：
[4, 5]，花費為abs(2 - 2) = 0 - 合併 1 和 2：
[9]，花費為abs(4 - 5) = 1
總花費為 4 + 0 + 1 = 5，因此輸出為 5。
範例 2 說明請見題目敘述的圖
標籤:
出處:
2024年1月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 40367 | 40970031H (twilight) | m934 | 616 | 2024-05-14 18:58 | |
| 39091 | nonamegogo (nonamegogo) | m934 | 1228 | 2024-01-12 23:02 | |
| 39043 |
|
m934 | 1632 | 2024-01-09 09:06 | |
| 40952 |
|
m934 | 263 | 2024-06-21 11:23 | |
| 40647 |
|
m934 | 402 | 2024-06-03 20:33 |