796 . 堆沙堡

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Tags

apcsc apcsc-dp

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

Sample Output 1

19

Sample Input 2

5
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
Submit
Back to Top