AGC062B 题解

· · 题解

妙妙题。

像这种最优化问题，数据范围又比较小，大概率不是贪心，想 dp。

正着做不好做，因为你无法知道序列变成了什么样子，没有任何信息能记录到状态里面。

考虑逆序操作。每次相当于取出一个子序列，放到后面。最终目标是将数组排成升序。

考虑区间 dp，设 f_{k,i,j} 为进行完第 k \sim K 次操作，已经把数组中值为 i \sim j 的数排好序。有转移：

初值是 f_{m+1,i,j} = 0，其中权值在 [i,j] 之中的数已经在原排列中排好序。

答案就是 f_{1,1,n}。

时间复杂度 O(n^3k)。

code