← 返回题目列表

AtCoder · typical90_s

019. 选二(★6)

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

配点: 6 点

問題文

长度 小于或等于 2N 的正整数序列 给出了 A=(A_1,A_2,\ldots,A_{2N}) 。 具有以下操作的列 考虑从 A 中删除一个数字。

  • 剩余列 满足 (A^{\prime}_1,A^{\prime}_2,\ldots,A^{\prime}_M) 。 1\leq i<M 的整数 选择 i ,A^{\prime}_i 和 按字典顺序比较 A^{\prime}_{i+1} 。执行此操作后,剩余的列是 (A^{\prime}_1,\ldots,A^{\prime}_{i-1},A^{\prime}_{i+2},\ldots,A^{\prime}_M) 。

此操作需要 成本 需要 。 1 操作的成本是删除的数量。 A^{\prime}_i,A^{\prime}_{i+1} 作为 |A^{\prime}_i-A^{\prime}_{i+1}| 。

此操作 执行 N 次 当从 A 中删除所有数字时, 求N 操作的最小可能总成本。

制約

  • 1 \leq N \leq 200
  • 1 \leq A_i \leq 10^6\ (1\leq i\leq 2N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_{2N}

出力

N 请输出运营总成本的最小可能值。


入力例 1

3
6 2 3 9 8 6

出力例 1

2

下面显示了最小化总成本的操作示例。 执行该操作的成本为

  • i=2 和|2 - 3| = 1 。该行是 (6,9,8,6) 变为。
  • i=2 和|9 - 8| = 1 。该行是 (6,6) 变为。
  • i=1 和|6 - 6| = 0 。该行是 () 变为。

3 总运营成本为 2 。 对于


入力例 2

3
1 3 5 5 3 1

出力例 2

0

入力例 3

4
1 2 4 8 16 32 64 128

出力例 3

85

入力例 4

15
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

出力例 4

207