← 返回题目列表

AtCoder · awc0049_e

E. 优化配送路线

中文机器翻译题面 查看原题

分数: 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