Nene 与 MEX 操作题解

思路

长度为 $k$ 的一段总能被变成 $k$ 个 $k$，因而贡献 $k^2$。先用单点操作把这一段全部变成 $0$。设递归过程要把一段全零数组变成 $0,1,\ldots,k-1$：先递归处理前 $k-1$ 个位置，对整段操作一次使其全部变成 $k-1$，再递归处理前 $k-1$ 个位置。最后对整段操作一次，其 MEX 为 $k$。

递归所用操作数满足 $T(k)=2T(k-1)+1$，再加清零和最后一次操作。即使 $k=18$，操作总数也远小于 $5\times10^5$。

因此最优方案等价于把数组划分成若干连续块：长度大于一的块可贡献块长平方；长度为一的位置可以保留原值，也可以变成 $1$。

做法

令 $f_i$ 表示前 $i$ 个位置能得到的最大和。可以保留第 $i$ 个数，从 $f_{i-1}+a_i$ 转移；也可以选取某个 $j\le i$，把区间 $[j,i]$ 整体变成长度 $i-j+1$，从

转移。记录每次最优转移，倒推得到所有需要变换的区间，再按上述递归构造逐段输出操作。

复杂度

动态规划时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。构造最多输出 $O(2^n)$ 次操作；在 $n\le18$ 时满足题目上限。