分数: 433 分
问题陈述
Takahashi 是一名送货员,需要将包裹递送至 N 房子。房子都有编号 1, 2, \ldots, N,以及房屋标高 i is V_i。标高不一定是明显的;不同的房屋可能具有相同的标高。
高桥开始在家 1。送货上门 1 已经完成,房子 1 已标记为已访问。高桥现在必须将包裹运送到所有剩余的房屋 2, 3, \ldots, N.
交货执行如下。高桥制作 N - 1 移动。在每次移动中,他都会从当前位置精确选择一栋未访问过的房屋,移动到该房屋,并将其标记为已访问。目的地不必是相邻的房屋;他可以直接搬到任何无人拜访的房子。一旦所有房屋都被访问过一次,交付就完成了。他到达哪个房子并不重要(他不需要返回房子 1).
直接从房子搬走的费用 i 到家 j 由以下公式确定,无论中间有什么房屋:
|V_i - V_j| \times |i - j|
换句话说,成本是标高的绝对差和门牌号的绝对差的乘积。
最小化总成本 N - 1 移动。
约束
- 1 \leq N \leq 20
- 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数。
输入
N V_1 V_2 \ldots V_N
- 第一行包含一个整数 N,代表房屋数量。
- 第二行包含 N 整数 V_1, V_2, \ldots, V_N 以空格分隔,代表每间房屋的标高。
输出
在一行上打印访问所有房屋一次所需的最小总移动成本。
示例输入 1
3 10 20 40
示例输出 1
30
示例输入 2
4 5 3 8 1
示例输出 2
13
示例输入 3
8 100 250 120 400 50 300 180 90
示例输出 3
950
示例输入 4
15 1000000000 0 500000000 250000000 750000000 125000000 875000000 62500000 937500000 31250000 968750000 15625000 984375000 7812500 992187500
示例输出 4
1921875000
示例输入 5
1 0
示例输出 5
0