D. Jellyfish and Mex - DP

本文主要是介绍D. Jellyfish and Mex - DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析：

题目最终需要达到MEX位0，也就是从最开始的MEX变成0后m的最小值，可以设$d{p}_i$表示当前MEX为$i$时，m的最小值，那么就可以根据前一个状态推出后一个状态，也就是假如当前MEX是$i$，那么对于1~$i$之间的$j$的所有每一种可能的MEX,都会有一个权值对应得到$d{p}_j$取最小值得到最小的m值，状态转移方程为$d{p}_j=min(d{p}_j,d{p}_i+i\ast a[j])$，最后$d{p}_0$也就是表示答案，但是第一次操作时m是0，所以第一次并没有加上初始的MEX，所以需要减去一个初始的MEX。

代码：

#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();}
}

这篇关于D. Jellyfish and Mex - DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---