分析

tag:DP

本质就是删除$v-1$、$v$、$v+1$获得$cnt[v]*v$的价值，我们记录出现的最大数字$maxx$，并且用$val$数组存删掉$v$的价值，从$1$~$maxx$进行$DP$，对于当前最优解有两种状态：删上一个或者删上上个，删上一个的最优解就是$dp[i-1]$，删上上个的最优解就是$dp[i-2]$ + $val[i]$，状态转移如下：

• $dp[0] = 0$
• i < 2 : $dp[i] = max(dp[i-1], val[i])$
• i >= 2: $dp[i] = max(dp[i-1], dp[i-2] + val[i])$

参考代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
long long dp[N];
long long val[N];
int main() {
    int n;
    scanf("%d", & n);
    vector < int > elements(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", & elements[i]);
    }
    int maxx = 0;
    for (auto it: elements) {
        val[it] += it;
        maxx = max(maxx, it);
    }
    long long ans = 0;
    for (int i = 1; i <= maxx; ++i) {
        dp[i] = max(dp[i - 1], (i < 2 ? 0 : dp[i - 2]) + val[i]);
        ans = max(ans, dp[i]);
    }
    printf("%lld\n", ans);
    return 0;
}