#1724. [Usaco2006 Nov]Fence Repair 切割木板

[Usaco2006 Nov]Fence Repair 切割木板

题目描述

Farmer John 想修理牧场栅栏的某些小段。为此,他需要 nn 块特定长度的木板,第 ii 块木板的长度为 lil_i。然后,FJ 去买了一块很长的木板,它的长度正好等于所有需要的木板的长度和。接下来的工作,当然是把它锯成需要的长度。FJ 忽略所有切割时的损失——你也应当忽略它。FJ 郁闷地发现,他并没有锯子来把这块长木板锯开。于是他把这块长木板带到了 Farmer Don 的农场,想向 FD 借用锯子。作为一个有商业头脑的资本家,Farmer Don 没有把锯子借给 FJ,而是决定帮 FJ 锯好所有木板,当然 FJ 得为此付出一笔钱。锯开一块木板的费用,正比于木板的长度。如果这块木板的长度是 2121,那么锯开它的花费便是 2121 美分。谈妥条件后,FD 让 FJ 决定切割木板的顺序,以及每次切割的位置。请你帮 FJ 写一个程序,计算为了锯出他想要的木板,他最少要花多少钱。很显然,按不同的切割顺序来切开木板,FJ 的总花费可能不同,因为不同的切割顺序,会产生不同的中间结果。

输入格式

  • 第一行:一个正整数 nn,表示 FJ 需要木板的总数。
  • 第二至 n+1n+1 行:每行包含一个整数,为 FJ 需要的某块木板的长度。

输出格式

  • 第一行:输出一个整数,即 FJ 完成对木板的 n1n-1 次切割的最小花费。
3
8
5
8
34

样例说明

FJ 打算把一块长为 2121 的木板切成长度分别为 8,5,88,5,8 的三段。

起初,木板的长度为 2121。第一次切割木板花费 2121 美分,把木板切成长分别为 131388 的两块。然后花费 1313 美分把长为 1313 的木板切成长为 8855 的两块。这样的总花费是 21+13=3421+13=34 美分。如果第一次把木板切成长为 161655 的两块,那么第二次切木板的花费就是 1616 美分,这样的总花费就是 3737 美分,比刚才花费 3434 美分的方案来的差。

数据规模与约定

对于 100%100\% 的数据,1n2×1041\le n\le 2\times 10^41li5×1041\le l_i\le 5\times 10^4

题目来源

Gold