#OJ2190. 级无敌简单的没法再简单的简单的大水题
级无敌简单的没法再简单的简单的大水题
级无敌简单的没法再简单的简单的大水题
Time Limit: 1 Sec Memory Limit: 128 MB
Description
农夫约翰为了修理栅栏,要将一块很长的模板切割成N块。准备切成的模板的长的为L1、L2、。。。Ln,未切割前的木板长度恰好为切割后木板长度的总和。每次切断木板时,需要的开销为这块木板的长的。例如长度为21的木板要切成长度为5、8、8的三块木板,长21的木板切成长为13和8的板时,开销为21。再将长度为13的板切成长度为5和8的板时,开销是13.于是合计开销为34。请求出按照目标要求将木板切割完最小的开销是多少? 限制条件 1<=N<=20000 0<=Li<=50000
Input
第一行输入N,第二行输入N个Li
Output
输出最小开销
Sample Input
3
8 5 8
Sample Output
34