top1编程
← 返回上一页

P4958. 合并石子

时间限制
1000 ms
内存限制
64 MiB
难度
-
知识点
童程童美
知识点
动态规划提高
知识点
区间DP

题目描述

在一个操场上一排地摆放着 NN 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 22 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 计算出将 NN 堆石子合并成一堆的最小得分。

输入格式

第一行为一个正整数 NN ( 2N1002\le N\le 100)。 以下 NN 行,每行一个正整数,小于 1000010000,分别表示第 ii 堆石子的个数(1iN1\le i\le N)。

输出格式

一个正整数,即最小得分。

7
13
7
8
16
21
4
18
239