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

选中a_i，删除数组中每一个a_i+1和a_i-1的数。可以遍历1到10000中的每一个数字，出现在给定的数组中就统计次数，因为最后也是需要输出得分的。

这样就是对数组counts进行动态规划

转移方程

数i 不选，它可以来自自身减一的数的两种状态的最大值

dp[i][0] = max(dp[i-1][0], dp[i-1][1])

数i 选，它只能来自自身减一的数在不选择的状态下，加上自身的分数（值*数量）

dp[i][1] = dp[i-1][0] + i * counts[i]

#include <iostream>
using namespace std;
int counts[10001]; //counts[a_i]记录a_i出现的次数， 1~10000内在给定的数组中没出现的就是0
int dp[100005][2];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        counts[x]++;
    }
    int maxx = 0;
    for (int i = 1; i <= 10000; i++) {
        //取
        dp[i][1] = dp[i - 1][0] + i * counts[i];
        //不取
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        maxx = max(dp[i][1], dp[i][0]);

    }
    printf("%d\n", maxx);
    return 0;
}