导航切换
Back
Overview
Status
Standings
Printer
Login
Login
Register
Start:
Oct, 04, 2021 14:00:00
动态规划强化练习题单
End:
Oct, 23, 2021 18:00:00
Time elapsed:
Time remaining:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
石子合并
【动态规划 DP专题训练】
1265
Time Limit:
1 Sec
Memory Limit:
128 MB
Submission：
7
AC：
1
Score：
100
Submit
Description
有n堆石子围成一个圆圈。现在需要把它们合并成一堆石子。每次合并时，只能合并相邻的两堆石子，所耗力气为两堆石子重量之和，合并得到的新堆的重量为原两堆重量之和。问最少需要耗费多少力气？ 数据规模：1<=n<=200，合并n堆石子最少需要耗费的力气不超过2*10^9。
Input
第一行一个整数n，第二行n个整数，表示顺序排列的每堆石子的重量。
Output
只有一行，该行只有一个整数，表示合并这n堆石子最少需要耗费的力气。
Samples
input:
3 1 3 5
output:
13
Submit