2023-10-01

题目

难度&重要性(1~10):5

题目来源

luogu

题目算法

解题思路

这道题一眼 dp。

我们需要考虑的是对于函数 \(\operatorname{mex}\) 的性质，假设当前 \(a\) 数组存在 \(0\sim x\)，则 \(\operatorname{mex}a=x+1\)。再记每一个数出现过 \(s_0,s_1,\cdots s_n\)，如果当前我将数字 \(i\) 全部取出，代价就为 \(s_i\times (x+1)\)，而之后的 \(\operatorname{mex}a=i\)。

那么一个很明显的贪心，我们需要先用最小的代价将 \(\operatorname{mex}a\) 变为 \(0\)，再去删除剩余的就不需要有任何代价了。

我们记 \(f_{i}\) 表示将 \(\operatorname{mex}a\) 变为 \(i\) 的最小代价。转移就是：

\[f_i=\begin{cases}\min\limits_{j=i+1}^{tot}\{f_j+s_i\times j\} & (j\not=tot)\\ \min\{f_j+(s_i-1)\times j\} & (j=tot)\end{cases} \]

这里的 \(tot\) 表示为初始数组 \(a\) 的 \(\operatorname{mex}\)。

时间复杂度为 \(O(n^2)\)。