3707：Sensor

题目描述

在一条直线上有n个传感器，已知每个传感器的位置。现需要在这些传感器之间建立一些一对一连接。这些一对一连接是互不相同的，即同一传感器若与多个传感器建立连接，则需要建立多个一对一连接。
传感器A的传输半径定义为，与传感器A建立连接的所有传感器到A的最远距离，也就是传感器A需要多大的功率能够到达所有建立连接的传感器。
对于两个不同的传感器A和B，我们定义传感器A影响传感器B，当且仅当A和B之间的距离不超过A的传输半径。注意，A影响B并不意味着B一定影响A，因为传感器A和传感器B的半径可能是不同的。被传感器A影响的传感器数量称为传感器A的Inference。
现在请你计算一种连接方案，使得n个传感器连通，并且所有传感器的Inference之和最小。

输入解释

输入包含多组数据，每组数据包含两行，第一行包含一个整数n (1 <= n <= 30)，表示传感器的数目，第二行包含n个整数，表示每个传感器的坐标位置，坐标范围是[0,1000000000(10^9)]。
输入到文件结束为止

输出解释

对于每组数据，输出一行包含一个整数，表示最小可能的Inference之和。

输入样例

3
1 3 7
5
3 4 2 5 1
6
1 2 4 8 16 32

输出样例

4
8
13

提示

假设我们把传感器根据输入顺序按照1, 2 …… n标号。
样例1：连接(1, 2) (2, 3)
样例2：连接(1, 2) (2, 4) (3, 1) (3, 5)
样例3：连接(1, 2) (2, 3) (2, 4) (4, 5) (4, 6)

来自杭电HDUOJ的附加信息

Author	ACRush@THU
Recommend	lcy

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 HDOJ 5th Anniversary Contest

源链接： HDU-3707

最后修改于 2020-10-25T23:06:15+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
10000/5000MS(Java/Others)	32768/32768K(Java/Others)