我们的目标是将一块完整的木板切割成 n 块,每块长度为 L1,L2,L3...Ln。切割后各个木块的长度总和与切割前的木板长度相等。
每次在一块木板上切一刀,代价等于该木板的长度。例如:
- 在长度为 21 的木板切一刀,变成两块木板,长度分别为 5,16,所需代价为 21
- 在长度为 16 的木板上再切一刀,变为两块木板,长度分别为 8,8,所需代价为 16
为了达到上述目标,求最小的切割代价是多少。
输入
- 第一行是整数 n(1≤n≤20000),表示要将原始木板切割成多少块
- 接下来 n 行,每行一个整数,表示最终每块小木板的长度,其中 1≤Li≤50000
输出
提示
2021/12/07
测试数据更新,以往通过代码不会重判,可尝试重新提交