CF455A补题-526互联

思路

取与不取的问题，用dp就行

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 1e5 + 10;

i64 dp[N];

void solve() {
    int n;
    cin >> n;
    map<int, int> mp;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x] ++;
    }
    dp[1] = mp[1];
    for (int i = 2; i <= 100000; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + 1ll * i * mp[i]);
    }

    cout << dp[100000];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t --) solve();

    return 0;
}