796 . 堆沙堡
Description
在一望無際的海灘上，有 $N$ 堆沙堡排成一排，其中由左到右第 $i (1\le i\le N)$ 個沙堡有重量 $a_i$。你想把所有沙堡合併成一個大沙堡，但為了維持美觀，你每次只能合併相鄰兩個沙堡。
當你將重量 $x$ 和 $y$ 的沙堡合併時會花你 $x+y$ 單位的力氣，且完成後新的沙堡將會在原來兩沙堡中間的位置，重量即為 $x+y$。與新沙堡相鄰的沙堡就是與舊沙堡相鄰的那些沙堡。
請你回答在這樣的操作下，合成大沙堡的最小力氣。
Input Format
輸入第一行是一個正整數 $N$，表示沙堡堆數。
輸入第二行有 $N$ 個空白分隔的整數 $a_1, a_2, \dots, a_N$，代表由左到右沙堡的重量。
輸入保證 $1\le N\le 500$，$1\le a_i\le 10^ 9$。
Output Format
輸出一行一個整數代表合成一座大沙堡的最小力氣。
Sample Input 1
3
4 3 5
4 3 5
Sample Output 1
19
Sample Input 2
5
7 1 9 5 2
7 1 9 5 2
Sample Output 2
55
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~12 | 無額外限制 | 100 |