← 返回题目列表

AtCoder · arc126_d

D. 纯直

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

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