问题 1371 --第三题 线段覆盖

1371: 第三题 线段覆盖

题目描述

  如果一个点在一条线段上(包括这个点是线段端点的情况),我们说“这条线段覆盖了这个点”。
 现有n个在一条水平直线上排列的点,请你编写程序计算一下:如果用3条线段覆盖所有的点,这3条线段的长度之和最小是多少?
注意:既然说是3条,当然就不允许某两条是首尾相接的,否则就是2条了,而且,任何线段的长度都要大于0。

输入

输入文件cover.in,第一行为整数n(6≤n≤100),表示点的数量。第二行有n-1个整数,表示各点到最左端的点的距离,单位是厘米。已知这些整数都不会超过40000。

输出

输出文件cover.out,文件中只有一个整数,表示用3条线段覆盖所有点时,它们长度之和的最小值,单位是厘米。

样例输入输出

输入#1 复制
6
1 4 10 15 17
输出#1 复制
9

提示

序号 标题 作者 发表时间 费用 订购数 操作