分数: 700 点
问题陈述
我们有 N 卡片编号 1, 2, ..., N。 卡 i (1 \leq i \leq N) 有一个整数 A_i 一侧用红色墨水书写并写有一个整数 另一面用蓝色墨水写有 B_i 。 最初,这些卡片按照 Card 的顺序从左到右排列 1 到卡 N,红色数字朝上。
判断是否可以有一个从左到右面朝上的非递减序列(即对于每个 i (1 \leq i \leq N - 1),正面朝上的整数 (i+1)左起第张牌不小于牌面朝上的整数 i左起第张卡)通过重复以下操作。如果答案是肯定的,请找出实现该目标所需的最少操作数。
- 选择一个整数 i (1 \leq i \leq N - 1)。 交换 i-th 和 (i+1)左起第张牌,然后翻转这两张牌。
约束
- 1 \leq N \leq 18
- 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N B_1 B_2 ... B_N
输出
如果不可能有非递减序列,则打印 -1。
如果可能,请打印实现该目标所需的最少操作数。
示例输入 1
3 3 4 3 3 2 3
示例输出 1
1
通过执行一次操作 i = 1,我们有一个序列 [2, 3, 3] 朝上,非递减。
示例输入 2
2 2 1 1 2
示例输出 2
-1
经过任意次数的操作后,我们得到了序列 [2, 1] 朝上,这不是非减的。
示例输入 3
4 1 2 3 4 5 6 7 8
示例输出 3
0
可能不需要任何操作。
示例输入 4
5 28 15 22 43 31 20 22 43 33 32
示例输出 4
-1
示例输入 5
5 4 46 6 38 43 33 15 18 27 37
示例输出 5
3