2026.3 抓跳结论

洛谷P15868 【MX-X26-T4】「Cfz Round 7」breakfast
感觉比 BC 简单很多倍啊！
题目那个操作就是选最多 \(k\) 个位置变大。
注意到，记 \(p_i\) 为最终序列中 \(i\) 第一次出现地位置（没有就是 \(n+1\)），那么那个前缀 \(\text{mex}\) 和就是 \(\sum\limits_{i=0}^{n}n-\max\limits_{j=0}^{i}p_j+1=(n+1)^2-\sum\limits_{i=0}^{n}\max\limits_{j=0}^{i}p_j\)。
考虑对后面那个 dp，记 \(dp_{i,j,k}\) 表示考虑到 \(p_i\)，用了 \(j\) 次操作，\(p\) 当前前缀最大值为 \(k\) 的最小和，可以发现转移的时候要用到 \(P_i\) 表示原序列中 \(i\) 第一次出现的位置（没有就是 \(n+1\)），\(cnt_{i,j}\) 表示原序列前 \(i\) 个位置中小于等于 \(j\) 的个数。
转移其实比较抽象：
\(dp_{0,j,k}\) 是简单的，就是 \(dp_{0,0,P_0}=P_0\)。
对于 \(dp_{i,0,k}\)，显然是 \(dp_{i,0,\max\limits_{j=0}^{i}p_j}=dp_{i-1,0,\max\limits_{j=0}^{i-1}p_j}+\max\limits_{j=0}^{i}p_j\)。
对于 \(dp_{i,j,k}\)，\(i>0\)，\(j>0\)，考虑 \(k\) 和 \(P_i\) 的大小关系：
当 \(k<P_i\)：可以发现这个时候必须要操作一次，且前 \(k\) 个位置要占得下 \(0\sim i\)，即 \(cnt_{k,i}>i\)。显然 \(dp_{i,j,k}\) 一定能被 \(\min\limits_{l=1}^{k-1}dp_{i-1,j-1,l}+k\) 转移，若 \(a_k<i\) 则 \(dp_{i,j,k}\) 还能被 \(dp_{i-1,j-1,k}+k\) 转移。
当 \(k=P_i\)：这个时候不用操作，也就是 \(dp_{i,j,k}=\min\limits_{l=1}^{k-1}dp_{i-1,j,l}+k\)。
当 \(k>P_i\)：显然是 \(dp_{i,j,k}=dp_{i-1,j,k}+k\)。
再维护一个前缀 \(\min\) 就能做到 \(O(n^3)\)。
做完了！