题解

思路

设原数组的 MEX 为 $M$。大于等于 $M$ 的元素不会影响后续 MEX，可以留到 MEX 变成零后再删除。

考虑当前 MEX 为 $i$，并希望下一次让它降到 $j<i$。必须删除值为 $j$ 的全部元素。前 $c_j-1$ 次删除后 $j$ 仍存在，每次代价都是 $i$；最后一次删除后 MEX 变成 $j$，本次代价为 $j$。因此这次变化的代价为

这把问题化成一个只向更小编号转移的最短路动态规划。

做法

统计每个小于 $M$ 的值的出现次数。令状态值表示当前 MEX 已经降到某个数时的最小累计代价，初始只有 $M$ 的状态为零。

按 MEX 从大到小枚举。对每个当前值 $i$，枚举所有 $j<i$，用 $i(c_j-1)+j$ 更新状态 $j$。最后状态零就是答案。

任何删除序列中，MEX 只会在某个尚存在的较小值被删光时下降，因此可以唯一分解成这些转移；每个转移的代价由上式精确给出。反过来，按任意一条状态转移链依次删光指定值，都能实现对应代价，所以动态规划与原问题等价。

复杂度

$M\le n$。每个测试用例的时间复杂度为 $O(M^2)$，空间复杂度为 $O(M)$。