分数: 800 点
问题陈述
给你正整数 N, K 和排列 P = (P_{1}, P_{2}, \dots, P_{NK}) of (1, 2, \dots, NK).
Alice 重复执行以下操作来排序 P 按升序排列。
- 选择整数 i 和 j (i\neq j) 其中 1 \leq i, j \leq NK,并交换 P_{i} 和 P_{j}。如果 |i - j| 是的倍数 N,爱丽丝得到 1 点。
爱丽丝排序 P 按照最少的操作次数升序排列,在这种情况下,她获得的分数总和最大。
输出 Alice 获得的积分总和。
约束
- 1\leq N\leq 500
- 1\leq K\leq 10
- (P_{1}, P_{2}, \dots , P_{NK}) 是一个排列 (1, 2, \dots, NK)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
P_{1} P_{2} \dots P_{NK}
输出
输出答案。
示例输入 1
3 2 1 6 5 3 2 4
示例输出 1
2
例如, P 可以通过如下四种操作按升序排序。
- 执行操作 (i, j) = (2, 5)。手术后, P = (1, 2, 5, 3, 6, 4).
- 执行操作 (i, j) = (4, 6)。手术后, P = (1, 2, 5, 4, 6, 3).
- 执行操作 (i, j) = (3, 5)。手术后, P = (1, 2, 6, 4, 5, 3).
- 执行操作 (i, j) = (3, 6)。手术后, P = (1, 2, 3, 4, 5, 6).
在上述四个操作中,Alice 得到 1 点从每个 1圣和 4次操作,所以 Alice 总共得到 2 点。
这个操作序列是排序的方法之一 P 以最少的操作次数升序排列,并最大化该条件下的点数总和,因此输出 2.
示例输入 2
1 1 1
示例输出 2
0
示例输入 3
4 6 10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
示例输出 3
7