← 返回题目列表

AtCoder · keyence2020_d

D. 交换和翻转

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

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