J. 石子合并

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

有n堆石子围成一个圆圈。现在需要把它们合并成一堆石子。每次合并时，只能合并相邻的两堆石子，所耗力气为两堆石子重量之和，合并得到的新堆的重量为原两堆重量之和。问最少需要耗费多少力气？数据规模：1<=n<=200，合并n堆石子最少需要耗费的力气不超过2*10^9。

第一行一个整数n，第二行n个整数，表示顺序排列的每堆石子的重量。

只有一行，该行只有一个整数，表示合并这n堆石子最少需要耗费的力气。

3
1 3 5