ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 AE: 线段覆盖
内存限制:128 MB
时间限制:1 S
题面:传统
评测方式:文本比较
上传者:
提交:481
通过:134
返回比赛
提交
提交记录
题目描述
如果一个点在一条线段上(包括这个点是线段端点的情况),我们说“这条线段覆 盖了这个点”。
现有n 个在一条水平直线上排列的点,请你编写程序计算一下:如果用 3 条线段覆 盖所有的点,这 3 条线段的长度之和最小是多少?
注意:既然说是 3 条,当然就不允许某两条是首尾相接的,否则就是 2 条了,而且, 任何线段的长度都要大于 0。
注意:每条线段至少包含两个点
输入格式
第一行为整数n(6 ≤ n ≤ 100 ),表示点的数量。第二行有n −1个 整数,表示其它各点到最左端的点的距离,单位是厘米。已知这些整数都不会超过 40000。
样例2:
输入:
7
9999 588 758 165 251 9998
输出
422
数据3:
输入
14
559 311 864 933 460 1000 676 569 84 465 338 960 588
输出:
585
输出格式
文件中只有一个整数,表示用 3 条线段覆盖所有点时,它们长 度之和的最小值,单位是厘米。
输入样例
复制
6 1 4 10 15 17
输出样例
复制
9
分类标签
2012第十届绍兴市少儿信息学竞赛复赛试题