原题链接

题解

1.alice的策略一定是从小到大一个一个拿
2.为了让alice拿不到某特定值的蛋糕，bob需要在alice拿它之前把它拿完
3.在最优策略中，bob一定可以从小拿到大
4.设此时bob要拿完第 \(i\) 类蛋糕，该类蛋糕个数为 \(k\) 则拿完这个蛋糕bob还有 \(i-k-1\) 个回合可以用，所以从前面 \([1,i-k-1]\) 个回合里看看能挑完几个
5.每挑完一类蛋糕，挑后面蛋糕能用的回合就少一

code

#include<bits/stdc++.h>
using namespace std;
int rounds[5005]={0};
int dp[5005]={0};
int main()
{
    ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        map<int,int> q;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            q[x]++;
        }

        int cnt=0;
        for(auto it:q)
        {
            rounds[++cnt]=it.second;
        }

        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            if(rounds[i]<i)
            {
                int hh=rounds[i];
                //printf("di %d ge, it take %d rounds to clean\n",i,hh);
                for(int j=i-hh-1;j>=0;j--)
                {
                    if((i-dp[j]-1)<hh+j) continue;
                    dp[j+hh]=max(dp[j+hh],dp[j]+1);
                    ans=max(ans,dp[j+hh]);
                }
            }
        }


        for(int i=1;i<=n;i++)
        {
            //printf("huihe:%d  nadiao:%d\n",i,dp[i]);
            rounds[i]=0;
            dp[i]=0;
        }
        cout<<q.size()-ans<<'\n';
    }
    return 0;
}