题目内容

多多现在需要你帮助解决一个难题，多多得到了一个由 $n$ 个整数 $a_1,a_2,…,a_n$ 构成的序列 $a$ 和额外的一个整数 $x$，多多的任务是排序序列 $a$ 使其变为正序列，其中只要序列 $a$ 满足 $a_1 \leq a_2\leq … \leq a_n$ 就认为是一个正序列。

为了让序列 $a$ 变成正序列，多多被允许可以重复多次做这样一个操作：选择序列 $a$ 中的一个整数 $a_i(1 \leq i\leq n)$ 且满足 $a_i>x$，然后交换 $a_i$ 和 $x$。

解题思路

给定长度为 $n$ 的序列 $a$ 和一个额外的数 $x$，每次只能选择一个满足 $a_i>x$ 的位置 $i$，将 $a_i$ 与 $x$ 交换。目标是使 $a$ 变为非递减序列，求最少操作次数，若无法完成则输出 -1。

动态规划建模

定义状态 $\mathrm{dp}[l][x_0]$ 表示当前已处理前缀，使得前缀末尾值为 $l$，当前 $x$ 的值为 $x_0$ 时所需的最少交换次数。为了压缩状态，注意：

• $l$ 必须是最后一次放入前缀的值（保证前缀非递减，只需与 $l$ 比较）。
• $x_0$ 是当前“背包”中的值。
• 初始状态为 $\mathrm{dp}[-1][x] = 0$，表示前缀为空，且初始 $x$ 值为给定的 $x$。