固定点题解

思路

从左到右处理原序列。设已经删除了 $d$ 个数，那么当前原下标为 $i$ 的元素如果被保留，它在新序列中的位置就是 $i-d$。因此它成为固定点的充要条件是 $a_i=i-d$。

令状态记录处理完一个前缀后，在恰好删除若干元素时最多能得到多少个固定点。对于当前元素有两种选择：删除它，删除数增加一；保留它，删除数不变，并在满足上述等式时增加一个固定点。所有操作序列都会唯一对应到这两类转移组成的一条路径。

做法

对每组数据建立二维表。初始时处理了零个元素、删除零个元素，可得到零个固定点，其余状态不可达。

依次处理每个元素。由处理前 $i-1$ 个元素并删除 $d$ 个的状态：

• 删除当前元素，转移到删除 $d+1$ 个的状态；
• 保留当前元素，转移到仍删除 $d$ 个的状态；若 $a_i=i-d$，固定点数量加一。

处理完整个序列后，从小到大寻找第一个能得到至少 $k$ 个固定点的删除数。若不存在则输出 $-1$。

该转移同时枚举了当前元素被删与被留的全部可能，因此没有遗漏。状态只保留相同前缀、相同删除数下固定点最多的方案；固定点更多的方案在后续任何相同操作下都不会更劣，所以取最大值不会影响最优答案。

复杂度

每组数据共有 $O(n^2)$ 个状态，每个状态进行常数次转移，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。