5935: 进阶1.2.2 围栏修复
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:102
解决:42
题目描述
约翰想修牧场周围的篱笆,需要 N 块(1≤N≤20000)木块,每块木板都具有整数长度 Li(1≤Li≤50000)米。他购买了一块足够长的木板(长度为 Li 的总和,i = 1,2,…,N),以便得到 N 块木板。切割时木屑损失的长度不计。
农夫唐向约翰收取切割费用。切割一块木板的费用与其长度相同。切割长度为 21 米的木板需要 21 美分。唐让约翰决定切割木板的顺序和位置。约翰知道以不同的顺序切割木板,将会产生不同的费用。帮助约翰确定他得到 N 块木板的最低金额。
农夫唐向约翰收取切割费用。切割一块木板的费用与其长度相同。切割长度为 21 米的木板需要 21 美分。唐让约翰决定切割木板的顺序和位置。约翰知道以不同的顺序切割木板,将会产生不同的费用。帮助约翰确定他得到 N 块木板的最低金额。
输入
第 1 行包含一个整数 N ,表示木板的数量。第 2 ~ N+1 行,每行都包含一个所需木板长度 Li 。
输出
一个整数,即进行 N-1 次切割的最低花费。
样例输入 复制
3
8
5
8
样例输出 复制
34