← 返回题目列表

AtCoder · ttpc2024_1_e

E. 重新旅行

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

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