题面文章来源:https://www.uudwc.com/A/Nx5jg/
分析:
题目最终需要达到MEX位0,也就是从最开始的MEX变成0后m的最小值,可以设 d p i dp_i dpi表示当前MEX为 i i i时,m的最小值,那么就可以根据前一个状态推出后一个状态,也就是假如当前MEX是 i i i,那么对于1~ i i i之间的 j j j的所有每一种可能的MEX,都会有一个权值对应得到 d p j dp_j dpj取最小值得到最小的m值,状态转移方程为 d p j = m i n ( d p j , d p i + i ∗ a [ j ] ) dp_j = min(dp_j, dp_i + i * a[j]) dpj=min(dpj,dpi+i∗a[j]),最后 d p 0 dp_0 dp0也就是表示答案,但是第一次操作时m是0,所以第一次并没有加上初始的MEX,所以需要减去一个初始的MEX。文章来源地址https://www.uudwc.com/A/Nx5jg/
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<ll> f(n + 1, inf);
for(int i = 0; i < n; i ++) {
ll x;
cin >> x;
if(x < n) a[x] ++;
}
int m = 0;
while(a[m]) m ++;
f[m] = 0;
for(int i = m; i >= 1; i --) {
for(int j = 0; j < i; j ++) {
f[j] = min(f[j], f[i] + i * a[j]);
}
}
cout << f[0] - m << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T --) {
solve();
}
}