D. Jellyfish and Mex - DP

题面

分析:

题目最终需要达到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+ia[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();
    }
}

原文地址:https://blog.csdn.net/m0_75129175/article/details/133500706

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月25日 20:36
常见加密和解密方法介绍。
下一篇 2023年10月25日 21:36