3176: POJ 3253 Fence Repair 栅栏修复

农夫 John（FJ）想对围着牧场的一小段栅栏作修补。他测量了栅栏长度，发现一共需要 N（1 ≤ N ≤ 20000）块木板，第 i 块木板的长度是 Li 个单位（1 ≤ Li ≤ 50000）。他买了一块长木板，其长度正好足够切成 N 块这样的木板。忽略每次锯木板的损失。 FJ 发现他并没有锯子，于是他带着这块长木板找到 Don 的农场去问她能不能借一把锯子。Don 并没有把锯子借给 FJ 而是向 FJ 收费，切一段木板一次的花销是木板的总长度。例如切一段 21 单位长的木板一次的花费是 21 单位。Don 让 FJ 决定且木板的顺序。请你帮助 FJ 计算把木板切成要求的 N 段需要的最小费用。切木板有很多种方式，不同切割方式会在切割过程中产生不同的中间长度，导致总花费不同。

第一行输入 N ，接下来 N 行输入每段木板的长度要求。

一个整数，即进行N -1次切割的最低花费。

3 8 5 8

34