#P1334. 瑞瑞的木板
瑞瑞的木板
题目背景
瑞瑞想要亲自修复在他的一个小牧场周围的围栏。
题目描述
他测量栅栏并发现他需要 根木板,每根的长度为整数 。于是,他买了一根足够长的木板,长度为所需的 根木板的长度的总和,他决定将这根木板切成所需的 根木板(瑞瑞在切割木板时不会产生木屑,不需考虑切割时损耗的长度)。
瑞瑞切割木板时使用的是一种特殊的方式,这种方式在将一根长度为 的木板切为两根时,需要消耗 个单位的能量。瑞瑞拥有无尽的能量,但现在提倡节约能量,所以作为榜样,他决定尽可能节约能量。显然,总共需要切割 次,问题是,每次应该怎么切呢?请编程计算最少需要消耗的能量总和。
输入格式
输入的第一行是整数,表示所需木板的数量 。
第 到第 行,每行一个整数,第 行的整数 代表第 根木板的长度 。
输出格式
一个整数,表示最少需要消耗的能量总和。
3
8
5
8
34
提示
输入输出样例 1 解释
将长度为 的木板,第一次切割为长度为 和长度为 的,消耗 个单位的能量,第二次将长度为 的木板切割为长度为 和 的,消耗 个单位的能量,共消耗 个单位的能量,是消耗能量最小的方案。
数据规模与约定
- 对于 的数据,保证 ,。