#193. 石子合并

石子合并

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

题目描述

设有N\red N堆石子排成一排,其编号为123N\red{1,2,3,…,N}

每堆石子有一定的质量,可以用一个整数来描述,现在要将这N\red{N}堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

例如有4\red{4}堆石子分别为1 3 5 2\red{ 1~ 3~ 5 ~2}, 我们可以先合并12\red{1、2}堆,代价为4\red{4},得到4 5 2\red{4 ~5 ~2}, 又合并 12\red{1,2}堆,代价为9\red{9},得到9 2\red{9 ~2 },再合并得到11\red{11},总代价为4+9+11=24\red{4+9+11=24}

如果第二步是先合并23\red{2,3}堆,则代价为7\red{7},得到47\red{4 7},最后一次合并代价为11\red{11},总代价为4+7+11=22\red{4+7+11=22}

问题是:找出一种合理的方法,使总的代价最小,输出最小代价。

输入格式

第一行一个数N表示石子的堆数N\red{N}

第二行N\red{N}个数,表示每堆石子的质量(均不超过1000)。

输出格式

输出一个整数,表示最小代价。

样例

输入样例

4
1 3 5 2

输出样例

22

提示

1N300\red{1≤N≤300}

少年宫集训队

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-9-25 15:30
结束于
2021-9-25 17:36
持续时间
2.1 小时
主持人
参赛人数
22