#O1037. 石子合并

石子合并

题目描述

有 nn 堆石子排成一排,第 ii 堆有 aia_i 个。每次只能把相邻两堆合并成一堆,消耗的代价为两堆石子数之和(新堆石子数为两者之和)。把 nn 堆合并成一堆的最小总代价是多少?

题目类型

区间动态规划

输入格式

第一行一个整数 nn。

第二行 nn 个整数 aia_i。

输出格式

一行一个整数,表示最小总代价。

样例 #1

样例输入 #1

4
1 3 5 2

样例输出 #1

22

数据规模与约定

数据范围 说明
1≤n≤2001 \le n \le 200 堆数
1≤ai≤1061 \le a_i \le 10^6 石子数
  • 用区间 DP:fl,rf_{l,r} 表示合并 [l,r][l,r] 的最小代价,O(n3)O(n^3) 可通过。