环形木牌

提高+/省选- CSP-S 区间动态规划模拟赛原创

题目描述

有 $n$ 块木牌围成一圈，第 $i$ 块木牌的重量为 $a_i$。每次可以选择相邻的两段木牌合并，代价为这两段内所有木牌重量之和。合并后仍视为一段木牌，直到所有木牌合成一段。

求总合并代价的最小值。

第一行输入一个整数 $n$。第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

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

$1 \le n \le 300$，$1 \le a_i \le 10^6$。

1
7

时间限制: 2500ms

内存限制: 256MB

通过率: 20.0%

提交数: 5