P16030

石子合并

难度 6 级小学动态规划入门区间DP

讨论统计 40通过 83提交 48.2%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

有n( $0 < n \leq 200$ )堆石子围城一圈，现要将石子合并成一堆。每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这n堆石子合并成一堆的总花费最小。

第1行为石子堆数 $n$ 。第2行为 $n$ 个数，表示每堆石子数，每两个数之间用一个空格分隔。

将石子合并为一堆的最小花费。

样例 1

输入

4
4 5 9 4

输出

起始每个石堆的数量不超过100

动规专题

上一题下一题