Almost Sorted

题意翻译

给定一个长度为 $n$ 的置换 $p$，以及一个正整数 $k$． 对于一个置换 $q$，要求对于所有满足 $1\leq i<j\leq n$ 的 $i,j$，有以下不等式成立： $$ p_{q_i}\leq p_{q_j}+k $$ 现在请求出满足条件的置换 $q$ 中，逆序对数最小的 $q$，它逆序对数是多少。 $1\leq n\leq 5000,1\leq k\leq 8$．

题目描述

You are given a permutation $ p $ of length $ n $ and a positive integer $ k $ . Consider a permutation $ q $ of length $ n $ such that for any integers $ i $ and $ j $ , where $ 1 \le i < j \le n $ , we have $ $p_{q_i} \le p_{q_j} + k. $ $ </p><p>Find the minimum possible number of inversions in a permutation $ q $ .</p><p>A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \[2,3,1,5,4\] $ is a permutation, but $ \[1,2,2\] $ is not a permutation ( $ 2 $ appears twice in the array) and $ \[1,3,4\] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).</p><p>An inversion in a permutation $ a $ is a pair of indices $ i $ and $ j $ ( $ 1 \\le i, j \\le n $ ) such that $ i &lt; j $ , but $ a\_i &gt; a\_j$.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 5000 $ , $ 1 \le k \le 8 $ ). The second line contains $ n $ distinct integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ).

输出格式

Print the minimum possible number of inversions in the permutation $ q $ .

输入输出样例

输入样例 #1

1 1
1

输出样例 #1

0

输入样例 #2

3 1
2 3 1

输出样例 #2

1

输入样例 #3

5 2
5 4 3 2 1

输出样例 #3

6

输入样例 #4

10 3
5 8 6 10 2 7 4 1 9 3

输出样例 #4

18

说明

In the first example, the only permutation is $ q = [1] $ ( $ 0 $ inversions). Then $ p_{q_1} = 1 $ . In the second example, the only permutation with $ 1 $ inversion is $ q = [1, 3, 2] $ . Then $ p_{q_1} = 2 $ , $ p_{q_2} = 1 $ , $ p_{q_3} = 3 $ . In the third example, one of the possible permutations with $ 6 $ inversions is $ q = [3, 4, 5, 1, 2] $ . Then $ p_{q_1} = 3 $ , $ p_{q_2} = 2 $ , $ p_{q_3} = 1 $ , $ p_{q_4} = 5 $ , $ p_{q_5} = 4 $ .

题目大意：
给定一个长度为 $n$ 的排列 $p$ 和一个正整数 $k$。需要找到一个排列 $q$，使得对于所有的 $1 \leq i < j \leq n$，都满足 $p_{q_i} \leq p_{q_j} + k$。需要求出满足条件的排列 $q$ 中，逆序对数最少的是多少。

输入输出数据格式：
输入格式：
- 第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 5000, 1 \leq k \leq 8$）。
- 第二行包含 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。

输出格式：
- 输出满足条件的排列 $q$ 的最小逆序对数。

输入输出样例：
输入样例 #1：
```
1 1
1
```
输出样例 #1：
```
0
```

输入样例 #2：
```
3 1
2 3 1
```
输出样例 #2：
```
1
```

输入样例 #3：
```
5 2
5 4 3 2 1
```
输出样例 #3：
```
6
```

输入样例 #4：
```
10 3
5 8 6 10 2 7 4 1 9 3
```
输出样例 #4：
```
18
```

说明：
- 在第一个例子中，唯一的排列是 $q = [1]$（0个逆序对）。
- 在第二个例子中，唯一有1个逆序对的排列是 $q = [1, 3, 2]$。
- 在第三个例子中，可能具有6个逆序对的排列之一是 $q = [3, 4, 5, 1, 2]$。题目大意： 给定一个长度为 $n$ 的排列 $p$ 和一个正整数 $k$。需要找到一个排列 $q$，使得对于所有的 $1 \leq i < j \leq n$，都满足 $p_{q_i} \leq p_{q_j} + k$。需要求出满足条件的排列 $q$ 中，逆序对数最少的是多少。 输入输出数据格式： 输入格式： - 第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 5000, 1 \leq k \leq 8$）。 - 第二行包含 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。 输出格式： - 输出满足条件的排列 $q$ 的最小逆序对数。 输入输出样例： 输入样例 #1： ``` 1 1 1 ``` 输出样例 #1： ``` 0 ``` 输入样例 #2： ``` 3 1 2 3 1 ``` 输出样例 #2： ``` 1 ``` 输入样例 #3： ``` 5 2 5 4 3 2 1 ``` 输出样例 #3： ``` 6 ``` 输入样例 #4： ``` 10 3 5 8 6 10 2 7 4 1 9 3 ``` 输出样例 #4： ``` 18 ``` 说明： - 在第一个例子中，唯一的排列是 $q = [1]$（0个逆序对）。 - 在第二个例子中，唯一有1个逆序对的排列是 $q = [1, 3, 2]$。 - 在第三个例子中，可能具有6个逆序对的排列之一是 $q = [3, 4, 5, 1, 2]$。