最高分数:300 积分
问题陈述
AtCoder Market 是一家超市,包括 1 \ 000 \ 000 \ 000 正方形,从左到右像直线一样连接。让“方 i“ i- 最左边的方块。换句话说,正方形 i 和正方形 i+1 连接所有整数 i \ (1 \leq i \leq 999 \ 999 \ 999).
有一天, N 买家来到AtCoder Market购物。 i第一个买家想要购买两件商品:一件是正方形的 A_i,另一个在正方形中 B_i.
AtCoder Market 的所有者 square1001 将安装一个 入口 和一个 退出.
入口和出口可以安装在任意广场,入口和出口可以放置在同一广场。
然后, i第买家将通过以下方式进行购物:
- 从入口开始,然后参观广场 A_i, B_i,并在出口处瞄准。他们将沿着最短路线移动。
对于所有买家来说,这完全需要 1 秒移动到相邻的方块。
业主最优选择出入口地点时,最少购物时长之和是多少?
约束
- 1 \leq N \leq 30
- 1 \leq A_i < B_i \leq 1 \ 000 \ 000 \ 000
子任务/评分
这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。
- (195分):1 \leq A_i < B_i \leq 100。另外,入口和出口都是方形的 1, 2, 3, ..., 100,在最优解中。
- (105分):没有额外的限制。
输入
输入将从标准输入给出,格式如下。
N A_1 B_1 A_2 B_2 : : A_N B_N
输出
在一行中打印购物持续时间的最小总和(以秒为单位)。
注意
在此约束下,答案可能不包含在 32位整数。
使用 64- 位整数,例如在C/C++中,我们可以使用 long long 类型,而不是 int.
示例输入 1
3 5 7 2 6 8 10
示例输出 1
18
考虑在广场安装入口 5,然后在广场退出 7。每位买家的行动如下:
- 买家编号1:方形 5 -> 6 -> 7
- 买家编号2:方格 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
- 买家编号3:方格 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7
(粗体字表示买家已拿货)
买家 1, 2, 3 将使用 2, 8, 8 秒,因此总购物时间将为 18 秒。
没有办法让总购物时间短于 18 秒。
示例输入 2
5 1 71 43 64 13 35 14 54 79 85
示例输出 2
334
square1001在广场安装入口时 14 并在广场退出 64,总购物时间将为 334 秒,并且是最小值。
示例输入 3
11 15004200 341668840 277786703 825590503 85505967 410375631 797368845 930277710 90107929 763195990 104844373 888031128 338351523 715240891 458782074 493862093 189601059 534714600 299073643 971113974 98291394 443377420
示例输出 3
8494550716
square1001在广场安装入口时 189 \ 601 \ 059 并在广场退出 715 \ 240 \ 891,总购物时间将为 8 \ 494 \ 550 \ 716 秒,并且是最小值。