#O1037. 石子合并
石子合并
题目描述
有 堆石子排成一排,第 堆有 个。每次只能把相邻两堆合并成一堆,消耗的代价为两堆石子数之和(新堆石子数为两者之和)。把 堆合并成一堆的最小总代价是多少?
题目类型
区间动态规划
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
一行一个整数,表示最小总代价。
样例 #1
样例输入 #1
4
1 3 5 2
样例输出 #1
22
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 堆数 | |
| 石子数 |
- 用区间 DP: 表示合并 的最小代价, 可通过。
有 n 堆石子排成一排,第 i 堆有 ai 个。每次只能把相邻两堆合并成一堆,消耗的代价为两堆石子数之和(新堆石子数为两者之和)。把 n 堆合并成一堆的最小总代价是多少?
区间动态规划
第一行一个整数 n。
第二行 n 个整数 ai。
一行一个整数,表示最小总代价。
4
1 3 5 2
22
| 数据范围 | 说明 |
|---|---|
| 1≤n≤200 | 堆数 |
| 1≤ai≤106 | 石子数 |