[Usaco2006 Nov]Fence Repair 切割木板

Farmer John 想修理牧场中的一些栅栏。为此，他需要 $N$ 块指定长度的木板，其中第 $i$ 块木板的长度为 $L_i$ 。

Farmer John 买来了一块长木板，其长度恰好等于所有所需木板的长度之和。他需要通过切割，将这块长木板分成指定的 $N$ 块木板。切割过程中产生的长度损失忽略不计。

由于 Farmer John 没有锯子，他请 Farmer Don 帮忙切割。每次切割一块木板时，费用等于被切割木板的长度。例如，切割一块长度为 $21$ 的木板需要花费 $21$ 美分。

Farmer John 可以自行决定切割顺序以及每次切割的位置。不同的切割顺序会产生不同长度的中间木板，因此总费用也可能不同。请计算完成全部 $N-1$ 次切割所需的最小总费用。

输入格式

第一行包含一个正整数 $N$ ，表示所需木板的数量。

接下来 $N$ 行，每行包含一个整数，其中第 $i$ 行的整数表示第 $i$ 块木板的长度 $L_i$ 。

输出一个整数，表示完成全部 $N-1$ 次切割所需的最小总费用。

需要将一块长度为 $21$ 的木板切割成长度分别为 $8$ 、 $5$ 、 $8$ 的 $3$ 块木板，最小总费用为 $34$ 美分。

本题为 USACO 2006 November 试题「Fence Repair」，题面与测试数据整理自 BZOJ。