问题 23815 --plank

23815: plank

时间限制: 1 Sec  内存限制: 128 MB
提交: 85  解决: 41
[提交][状态][讨论版][命题人:]

题目描述

农民 John 希望修复围绕农场的一小段围栏。他测量了一下,发现需要 N (1 <= N<= 20,000)根木头,每根都有某一个整数长度 Li (1 <= Li <= 50,000) 单位长度。他买了一根很长的很长的木头,正好能够锯出他所需要的 N 根木头。(即它的长度正好等于 Li 的总和) FJ 忽略锯口,锯掉的木屑产生的长度损失忽略不计,你也可以忽略它。FJ 遗憾的发现他自己没有用于切木头的锯子,所以他就带着那根很长的木头来到了农民Don 的农场,想问他借一个锯子。农民 Don 是一个保守的资本家,他不愿意借锯子给 FJ ,但愿意自己来切这 N-1 刀,每一次都向 FJ 收取费用。每次的收费正好等于你要锯的那根木头的总长度。例如,你要锯一根长度为 21 的木头,就花费 21 分钱。农民 Don 然后让农民 John 自己决定每次锯木头的顺序和位置。帮助农民 John 确定锯出这 N 根木头的最小总花费。 FJ 知道可以有很多种不同的切割方式,不同的方式可能得到不同的总花费,这是因为木头在锯的过程中的长度不一。

输入

* Line 1: 一个整数 N,表示要锯出的木头数
* Lines 2..N+1: 每行一个整数,表示每根木头的长度。

输出

* Line 1: 一个整数,表示他最少需要多少分钱,锯 N-1 下,锯出所有需要的木头。

样例输入

3
8
5
8

样例输出

34

来源

 

[提交][状态]