分数: 100 点
问题陈述
关于 xy-平面,有 N 标记点 1, 2, \dots, N.点的坐标 i (1 \le i \le N)是 (X_i, Y_i).
在这个平面的原点有一个机器人。你的任务是控制机器人访问所有点 1, 2, \dots, N 按此顺序.
机器人有一个字符串变量 S,最初是一个空字符串。
您可以使用以下四种类型的操作来移动机器人:
- 操作 1: 增加机器人的 x 坐标 1 并附加
X到年底 S。此操作成本 1. - 操作 2: 增加机器人的 y 坐标 1 并附加
Y到年底 S。此操作成本 1. - 操作 3: 减少机器人的 x 坐标 1 并删除最后一个字符 S。仅当最后一个字符 S is
X。此操作成本 0. - 操作 4: 减少机器人的 y 坐标 1 并删除最后一个字符 S。仅当最后一个字符 S is
Y。此操作成本 0.
求机器人访问所有点所需的最小成本 1, 2, \dots, N 按此顺序。
约束
- 所有输入值均为整数。
- 1 \le N \le 500
- 0 \le X_i, Y_i \le 10^9
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
输出机器人按顺序访问所有点所需的最小成本。
示例输入 1
2 3 3 1 2
示例输出 1
6
通过执行操作 1 一次,操作 2 三遍,然后操作 1 两次,即可到达点 1.
然后,通过执行操作 3 两次并操作 4 一次,即可达到点 2.
这一系列操作的总成本是操作次数的总和 执行 1 和 2 ,即 6.
示例输入 2
3 2 2 3 3 1 3
示例输出 2
7