有 $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)$,相鄰兩個數字之間用空格隔開。
子題分數:
輸出最小花費。
4 3 -1 2 5
5
6 -5 3 0 -4 3 -2
18
7 -1 -6 6 -8 7 0 -9
36
範例 1 說明:
[3, -1, 2, 5]
[2, 2, 5]
,花費為 abs(3 - (-1)) = 4
[4, 5]
,花費為 abs(2 - 2) = 0
[9]
,花費為 abs(4 - 5) = 1
總花費為 4 + 0 + 1 = 5
,因此輸出為 5
。
範例 2 說明請見題目敘述的圖
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
40367 | 40970031H (twilight) | m934 | 659 | 2024-05-14 18:58 | |
39091 | nonamegogo (nonamegogo) | m934 | 1271 | 2024-01-12 23:02 | |
39043 | sophie198205 ... (闕河正) | m934 | 1712 | 2024-01-09 09:06 | |
40952 | glps1004@gma ... (Ian) | m934 | 299 | 2024-06-21 11:23 | |
40647 | john1100729@ ... (靖諺) | m934 | 435 | 2024-06-03 20:33 |