A. Boredom

题解：简单DP，用a数组保存每个数字各自出现了几次，然后对于ans[i]如果选择了这个数那么之前的只能选择ans[i-2]+i*a[i]，或者之前的ans[i-1]

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x7f7f7f7f;

ll a[N];
ll ans[N];

int main(){
    int n;cin >> n;
    int ans1 = 0,ans2 = 0;
    for(int i = 1;i <= n;i++){
        int x;cin >> x;
        a[x]++;
    }
    ans[1] = a[1];
    for(int i = 2;i <= 100002;i++){
        ans[i] = max(ans[i-1],ans[i-2]+i*a[i]);
//        cout<<ans[i]<<endl;
    }
    cout<<ans[100002]<<endl;
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：A. Boredom，转载请注明来源！