有一个长度为 ∑ai\sum a_i∑ai 的木板,需要切割成 nnn 段,每段木板的长度分别为 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an。
每次切割,会产生大小为被切割木板长度的开销。
请你求出将此木板切割成如上 nnn 段的最小开销。
第 111 行一个正整数表示 nnn。
第 222 行包含 nnn 个正整数,即 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an。
输出一个正整数,表示最小开销。
5 5 3 4 4 4
47
对于全部测试数据,满足 1≤n,ai≤1051 \le n, a_i \le 10^51≤n,ai≤105。
原题:[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
需要 O(n)O(n)O(n) 解法的 数据加强版(1≤n≤1071 \le n \le 10^71≤n≤107)
使用您的 代码源 OJ 通用账户