分数: 600 点
问题陈述
给定的是一系列 N 正整数 A = (A_1, A_2, \ldots, A_N),其中每个 A_i is 1, 2, \ldots,或 K.
您可以对此序列执行以下操作任意次。
- 交换两个相邻元素,即选择 i 和 j 这样 |i-j|=1 并交换 A_i 和 A_j.
求出需要进行的最少操作数 A 满足以下条件。
- A 包含 (1, 2, \ldots, K) 为连续子序列,即存在正整数 n 最多 N-K+1 这样 A_n = 1, A_{n+1} = 2, \ldots,和 A_{n+K-1} = K.
约束
- 2\leq K\leq 16
- K \leq N\leq 200
- A_i is 1, 2, \ldots,或 K.
- A 包含至少出现一次以下各项 1, 2, \ldots, K.
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \ldots A_N
输出
打印完成所需的最少操作数 A 满足条件。
示例输入 1
4 3 3 1 2 1
示例输出 1
2
一种最佳操作顺序如下。
- 交换 A_1 和 A_2,改变 A to (1,3,2,1).
- 交换 A_2 和 A_3,改变 A to (1,2,3,1).
- 现在我们有 A_1 = 1, A_2 = 2, A_3 = 3,满足条件。
示例输入 2
5 5 4 1 5 2 3
示例输出 2
5
示例输入 3
8 4 4 2 3 2 4 2 1 4
示例输出 3
5