题解

思路

不被移动的球相对顺序不变，因此它们必须构成递增子序列。一个零球可以连续移动原排列中的一段球，所以被移动位置在原排列中至多形成 $k$ 个连续段。

做法

令 $f[i][r]$ 表示保留位置 $i$，且在它之前已经使用 $r$ 个删除段时，最多能保留多少个球。若第一个保留位置不是开头，前缀删除段计一次。由保留位置 $x$ 转移到 $i$ 时必须满足 $c_x<c_i$；若两位置不相邻，中间非空删除段再计一次。

最后根据末尾是否还有删除后缀补一次段数。对每个允许段数 $k$ 取最多保留球数，答案为 $n$ 减去它。把整个排列作为一个删除段也保证有解。

小规模可枚举保留位置集合；原排列升序时无需移动任何球。

复杂度

每组时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。