CF1875D Jellyfish and Mex

思路

看到 \(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;
}