题解 | #删除相邻数字的最大分数#

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e4 + 10;
int sum[N]{0};// sum[i]: 表示 i 出现的次数的分值总和 
int f[N]{0};  // f[i]: 表示选到 i 位置时，i 位置的元素必选，此时的最大分数
int g[N]{0};  // g[i]: 表示选到 i 位置时，i 位置的元素不选，此时的最大分数
int n = 0;
int x = 0;

int main()
{
    // 1. 输入及预处理
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        sum[x]+=x;
        // 不是sum[x]++的原因: 
        //      x被选了后，x-1和x+1都会被删了
        //      再次遇到x时，分值直接+x即可
    }

    // 2. 填表
    for (int i = 1; i < N; ++i)
    {
        f[i] = g[i-1] + sum[i];
        g[i] = max(f[i-1], g[i-1]);
    } 

    // 3. 输出结果
    cout << max(f[N-1], g[N-1]);
    return 0;
}