题解 CF1875D【Jellyfish and Mex】

标签：Mex 删除 题解 ll cin operatorname define mex Jellyfish

显然，除非 \(\operatorname{mex}a=0\)，否则不会删除 \(>\operatorname{mex}a\) 的数。而 \(\operatorname{mex}a=0\) 时不对答案产生贡献，因此任意时刻我们都可以忽略 \(a\) 中 \(>\operatorname{mex}a\) 的数。

又显然，一旦我们开始删一个数，就会先把所有与之相等的数删光。否则，设最先删光的数为 \(x\)，把所有删除 \(x\) 的操作提到最前面一定更优。

至此，我们自然地设 \(f_i\) 表示假设只保留所有 \(<i\) 的数，此时删光的最小代价。注意到，我们忽略了 \(>\operatorname{mex}a\) 的数，此时 \(i\) 的取值范围是 \([0,\operatorname{mex}a]\)，由 \(\operatorname{mex}\) 的定义可知此时 \(\operatorname{mex}a=i\)。

考察首先要删光哪个数，不妨设为 \(j\)（\(j < i\)）。设 \(j\) 出现次数为 \(cnt(j)\)。显然，前 \(cnt(j)-1\) 次删除时 \(j\) 还未被删光，此时对答案贡献为 \(i\)；最后一次删除时 \(j\) 已被删光，此时对答案贡献为 \(j\)。删除结束后，剩余的数列满足保留了所有 \(<j\) 的数，且 \(\operatorname{mex}a=j\)。此时，所有 \([j+1,i-1]\) 的数都可以被忽略，问题转化为 \(f_j\)。因此，得到转移方程：

\[f_i= \begin{cases} 0,&i=0\\ \min\limits_{j<i}\{f_j+(cnt(j)-1)\times i+j\},&i>0 \end{cases} \]

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

// Problem: D. Jellyfish and Mex
// Contest: Codeforces - Codeforces Round 901 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1875/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
    uniform_int_distribution<ll> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 5e3 + 5, inf = 0x1f1f1f1f1f1f1f1fll;

ll T, n, a[N], cnt[N], dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; T--) {
        cin >> n;
        rep(i, 1, n) {
            cin >> a[i];
            if(a[i] <= n) ++cnt[a[i]];
        }
        ll mex = 0;
        while(cnt[mex]) ++mex;
        rep(i, 1, mex) dp[i] = inf;
        rep(i, 1, mex) rep(j, 0, i - 1) chkmin(dp[i], dp[j] + (cnt[j] - 1) * i + j);
        cout << dp[mex] << endl;
        rep(i, 0, n) cnt[i] = 0;
    }
    return 0;
}

标签：Mex,删除,题解,ll,cin,operatorname,define,mex,Jellyfish
From： https://www.cnblogs.com/ruierqwq/p/CF-1875D.html