题目描述
难度分:$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;
}