题解 | Boredom

#include<bits/stdc++.h>
using namespace std;
#define int long long    
vector<int>cnt(100001),dp(100001);

void solve() {
    int n;cin>>n;
    vector<int>a(n);
    int max_a=0;
    for(int i=0;i<n;i++){
        cin>>a[i];cnt[a[i]]++;
        max_a=max(max_a,a[i]);
    }
    dp[1]=cnt[1];
    for(int i=2;i<=max_a;i++)
        dp[i]=max(dp[i-1],dp[i-2]+i*cnt[i]);
    cout<<dp[max_a];
}//把相同的数放在一起当成一个整体，然后排序（当然并不是说有排序这个步骤），题目就变成了求相邻值不能选的最大和，然后需要注意的是dp[i]表示的是从最大数为i时的最大和。然后根据这个去递推状态。

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}
// 64 位输出请用 printf("%lld")