TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1755
  • 题目
  • P1755修围栏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    农夫John想要修理农场的一段围栏。他测量了一下这段围栏,发现他需要N(1<=N<=20000)块木板,每块都有一定的长度Li(1<=Li<=50000)。后来他买了一块很长的木板,足以切割成N块(该木板的长度恰好是所需N块木板长度的总和)。

    突然,John悲催地意识到他没有锯子来锯木板。于是他带着他的长木板来到邻居农夫Don的农场,并礼貌的向Don提出借用锯子的请求。

    贪婪的Don不愿免费借锯子给John。John需要进行N-1次切割,Don提出每次切割需要支付一定的费用才行。每次切割的费用恰好等同于这次切割的木板的长度。比如切割长度为21的木板,需要支付21美分。

    Don让John决定从木板上切割的位置。John知道不同的切割顺序会有不同的花费。请问怎样切割才能让John以最小的总费用得到N块所需的木板,请你帮帮John。

    输入格式

    第一行,一个整数N,表示所需木块的数量。
    接下来N行,每行一个整数,表示所需木块的长度。

    输出格式

    一个整数,表示将木板个N-1次的最小花费。

    样例输入 1

    3
    8
    5
    8

    样例输出 1

    34

    样例输入 2

    5
    567
    345
    690
    1278
    841

    样例输出 2

    8354

    提示

    John想要把长度为21的木板切割成8,5,8

    最初木板的长度为8+5+8=21. 第一次切割会花费21, 把木板切割成13和8。第二次切割的花费为13, 把长度为13的木板切成8和5。这样切割的总费用是21+13=34。

    如果先把21切割成16和5,然后再把16切割成8和8,所需总费用就是37,这种方案就没有第一种花费34的方案优。


    来源  USACO 2006 November Gold Fence Repair root翻译