GCC版本升级到4.9.2,大家再也不用因为头文件而导致本地编译通过而网站通不过了。fpc版本为2.6.4。Java版本为1.8.0_45。

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

1072: 【基础】线段覆盖

时间限制 : 1 Sec
内存限制 : 16 Mb
提交 : 3498
解决 : 1482

题目描述

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

输入

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

输出

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

样例输入 [复制]

6 1 4 10 15 17

样例输出 [复制]

9

提示[+]

*** 提示已隐藏,点击上方 [+] 可显示 ***

来源

2008年北京市小学生程序设计网上练习赛一试试题(5)


Problem 1072
全 屏
重置代码