CF1875D Jellyfish and Mex

One_JuRuo · 2023-10-01 09:58:43 · 题解

思路

看到 n 的范围只有 5000，并且 \sum n 的范围也是 5000，所以可以考虑 n^2 的做法。

每次操作肯定都是一次性删完某个数字，如果删除某个数字删一半又去删别的数字，答案肯定会变大。

所以我们可以考虑统计所有数字的数量，记为 num_i，来计算删完某个数字的最小答案，记为 ans_i。

那么我们可以考虑用大于 i 的 j 来更新 ans_i，j 代表上一次删除的是 j，所以当前的 \operatorname{mex} 应该就是 j，那么删除 i 得到的值应该是 (num_i-1)\times j+i，因为删除的前 (num_i-1) 次的 \operatorname{mex} 是 j，最后一次是 i。

所以我们只需要倒着求 ans_i 即可，最后的答案是 ans_0。

另外，统计 \operatorname{mex} 以内的数即可，大于 \operatorname{mex} 的数都是无用的。并且，在这个方法没有删除的数字就最后挨个删除就好，反正 \operatorname{mex} 都是 0 没有影响。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,n,a[5005],now,num[5005],dp[5005][5005],ans[5005];
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n),now=num[0]=0;
        for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
        sort(a+1,a+n+1);//排序
        for(int i=1;i<=n;++i)
        {
            if(a[i]==now) ++num[now];//统计num，now最后就是mex
            else if(a[i]==now+1&&num[now]) num[++now]=1;
            else break;
        }
        if(!num[0]){printf("0\n");continue;}//mex最开始就是0
        ans[now+1]=0;//预处理
        for(int i=now;i>=0;--i)
        {
            ans[i]=0x3f3f3f3f;//赋初值
            for(int j=i+1;j<=now+1;++j) ans[i]=min(ans[i],ans[j]+(num[i]-1)*j+i);//更新答案
        }
        printf("%lld\n",ans[0]);
    }
    return 0;
}