问题1072--【基础】线段覆盖

1072: 【基础】线段覆盖

时间限制: 1 Sec  内存限制: 16 MB
提交: 3791  解决: 1576
[提交] [状态] [讨论版] [命题人:]

题目描述

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

输入

第一行为整数n(6 <= n <= 100 ),表示点的数量。 之后 n-1 行,每行一个整数,表示其它各点到最左端的点的距离,单位是厘米。已知这些整数都不会超过40000。

输出

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

样例输入

6
1
4
10
15
17

样例输出

9

来源/分类


[提交] [状态]