3214. 锯栅栏

单点时限: 2.0 sec

内存限制: 256 MB

约翰正在修复农场的一段围栏。进过丈量,他需要 块木板,第 块木板的长度应该是 。他订购了一根很长的木料,长度就是这 块木板的总长度,由于约翰没有锯子,所以他找到了老唐,想让他帮忙锯开木料。

老唐是个生意精,他乐意代劳,但劳动不是无偿的。每开动一次锯子,可以把木料锯成两段,锯出 块木板就需要开动 次机器。老唐说,每次开机都要收加工费,加工费用正比于需要锯开的木料长度。比如要把一段长 20 米的木料锯开,就要收 20 元。约翰不得不接受了老唐的要求,但他发现不同的切割次序会产生不同的费用。请帮约翰设计一个锯开木料的方案,使得约翰付出的加工费之和最小。

输入格式

第一行:单个整数

第二行到第 行:第 行有一个整数

输出格式

单个整数:表示约翰付出的最小费用

样例

Input
3
8
5
8
Output
34

46 人解决,53 人已尝试。

59 份提交通过,共有 162 份提交。

3.7 EMB 奖励。

创建: 2 年,8 月前.

修改: 2 年,4 月前.

最后提交: 2 周,1 天前.

来源: USACO

题目标签
STL