ARC204B - Sort Permutation 笔记

首先将每个数当前的位置 $i$ 和其要去的位置 $P_i$ 连有向边，容易发现形成了若干个环。

由于题目要求要在操作次数最小的前提下，因此每次必须是操作环上相邻的两个节点。

假设当前环按顺序组成的点集是 $Q$。

操作相邻的两个节点后，相当于交换了入边，其中一个节点归为变成独立的连通块，它两边的点成为了相邻的点。

假如将操作看成对这一段区间的操作，那么就肯定是一个个大区间包含着小区间，不会有交叉的情况。

因此，将操作的两个点连边，最后一定能够形成一棵树，满足树上的祖先节点对应环上操作一个大区间，儿子节点对应环上操作一个被大区间覆盖的小区间。

因此，如果一棵子树的根节点对应到环上的节点 $Q_L$，则其儿子必然是 $Q_{[L,R]}$ 的一段区间。

这样子是多叉树的，不好解决，可以让 $Q_L$ 只有两个儿子，左儿子内都是不能造成贡献的，右儿子和 $Q_L$ 造成了贡献，可以发现这样子操作是对的。

于是设 $f_{l,r}$ 表示将环上 $Q_{[l,r]}$ 的点组成子树后，贡献的最大值。

$$f_{l,r}\leftarrow f_{l+1,r}$$$$f_{l,r}\leftarrow f_{l+1,k}+f_{k,r}$$

方程式 $(1)$ 表示只有一个左子树，没有右贡献的右子树。

方程式 $(2)$ 当且仅当 $Q_k$ 能够对 $Q_l$ 做出贡献，因此这一部分转移是 $O(k)$。

状态数有 $O(n^2{k}^2)$。

时间复杂度 $O(n^2{k}^3)$，空间复杂度 $O(n^2{k}^2)$。