题解

思路

设最终选中的 $K$ 个元素原位置依次为 $i_1<i_2<\cdots<i_K$。

做法

若它们被移动到某个连续的 $K$ 个位置，则最少交换次数等于位置移动距离之和，再加上所选元素值序列的逆序对数。连续目标段的最优位置可令其中位位置与 $i_m$ 重合，其中 $m=\lceil K/2\rceil$；展开绝对值后，位置代价成为各 $i_j$ 的线性组合加一个只与 $K$ 有关的常数。

从左到右扫描原序列，令 $dp[S]$ 表示已经选过的数值集合为 $S$ 时线性位置代价与逆序对代价的最小和。若当前位置的值 $v\notin S$，它作为第 $|S|+1$ 个所选元素，加入相应位置系数，并增加 $S$ 中大于 $v$ 的数值个数作为新逆序对，即可转移到 $S\cup\{v\}$。

复杂度

最后补上展开时的常数，时间复杂度为 $O(N2^K)$，空间复杂度为 $O(2^K)$。