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 < j $ , but $ a\_i > 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 $ .