题目描述

难度分:$1600$

输入$T(\leq 5000)$表示$T$组数据。所有数据的$n$之和$\leq 5000$。

每组数据输入$n(1 \leq n \leq 5000)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

每次操作，你可以删除一个$a[i]$，代价为删除后的数组的MEX，即不在数组中的最小非负整数。

输出清空数组$a$（操作$n$次）的最小总代价。

输入样例

4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3

输出样例

3
0
2
7

算法

动态规划

这个题的数据范围很容易让人定位到动态规划的解法，但状态定义不太容易想。比较容易发现的一点就是，$a$数组中大于自身MEX的元素是没有必要删除的，因为删它们没有办法降低删除代价。而一旦整个数组的MEX$=0$，那删除剩下的元素就不需要任何代价，所以我们的目的就是让$a$的MEX降到$0$。

状态定义

$dp[i]$表示数组$a$的MEX$=i$所需要的最小删除代价，在这个定义下，答案就是$dp[0]$。

状态转移

倒序遍历$i \in [1,$MEX$]$，其中MEX是数组$a$的初始MEX。对于每个MEX，枚举要删除的数$j \lt i$，删除$cnt[j]-1$个$j$的代价都是$i$（因为$j$没有删干净时，MEX始终都是$i$），删除最后一个$j$就会使得MEX$=j$。因此，状态转移方程为$dp[j]=min_i(dp[i]+(cnt[j]-1) \times i + j)$，其中$cnt[j]$为$j$在$a$中的频数。

复杂度分析

时间复杂度

由于MEX的长度会受到$a$数组的长度限制，在最差情况下就是$a$数组中$0$到$n-1$都有，此时MEX$=n$，其他情况根据抽屉原理，都会使得MEX$\lt n$。所以状态的数量为$O(n)$级别，而单次转移需要遍历$j \lt i$，也是$O(n)$级别，整个算法的时间复杂度为$O(n^2)$。

空间复杂度

由于$a[i] \leq 10^9$，需要开一个哈希表$cnt$来记录数组中每个数值的频数，最差情况下有$O(n)$个键值对。根据对时间复杂度的分析，DP数组的空间也是$O(n)$级别。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5001;
int t, n, a[N], dp[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &t);
    unordered_map<int, int, custom_hash> cnt;
    while(t--) {
        scanf("%d", &n);
        cnt.clear();
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            cnt[a[i]]++;
        }
        int mex = 0;
        while(cnt.find(mex) != cnt.end()) mex++;
        memset(dp, 0x3f, sizeof(dp));
        dp[mex] = 0;
        if(mex == 0) {
            puts("0");
        }else {
            for(int i = mex; i >= 1; i--) {
                // 大于mex的元素不用删
                for(int j = 0; j < i; j++) {
                    dp[j] = min(dp[j], dp[i] + (cnt[j] - 1)*i + j);
                }
            }
            printf("%d\n", dp[0]);
        }
    }
    return 0;
}