题目思路

直接使用动态规划解决，$dp[0][i]$ 代表只考虑不大于i的数并且没有操作等于i的数时得到的最高得分，$dp[1][i]$ 代表只考虑不大于i的数并且操作了所有等于i的数时得到的最高得分，因为操作了 $i$ 就要删除所有等于 $i+1$的数，所以转移方程：

$dp[0][i] = max(dp[0][i-1], dp[1][i-1])$ $dp[1][i] = dp[0][i-1] + i*cnt[i]$

代码

Python代码

N = 10**5+1
cnt = [0]*(N)	#每个数的出现次数
n = int(input())
a = map(int,input().split())
for i in a:
	cnt[i] += 1
dp = [[0]*(N), [0]*(N)]
for i in range(1, N):
	dp[0][i] = max(dp[0][i-1], dp[1][i-1])
	dp[1][i] = dp[0][i-1] + i*cnt[i]
print(dp[0][N-1])

C++代码

#include <iostream>
using namespace std;
int cnt[100005],a[100005];
int dp[2][100005];
int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    for (int i=0;i<n;i++)
        cnt[a[i]]++;
    for (int i=1;i<=100000;i++)
    {
        dp[0][i]=max(dp[0][i-1],dp[1][i-1]);
        dp[1][i]=dp[0][i-1]+i*cnt[i];
    }
    cout<<dp[0][100000]<<endl;
    return 0;
}

Java代码

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int N = 100001;
        int[] cnt = new int[N];
        int[] a = new int[N];
        int[][] dp = new int[2][N];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            cnt[a[i]]++;
        }
        for (int i = 1; i <= 100000; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1]);
            dp[1][i] = dp[0][i - 1] + i * cnt[i];
        }
        System.out.println(dp[0][100000]);
    }
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
    //遍历数组，统计数组的和
    input=input.split('\n');
    let n=Number(input[0].split(' ')[0]);
    let N=100000+1;
    let cnt=new Array(N).fill(0);
    let a=new Array(N).fill(0);
    let dp=new Array(2);
    dp[0]=new Array(N).fill(0),dp[1]=new Array(N).fill(0);
    for (let i=0;i<n;i++){
        a[i]=Number(input[1].split(' ')[i]);
        cnt[a[i]]+=1;
    }
     for (let i = 1; i <= 100000; i++) {
         dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1]);
         dp[1][i] = dp[0][i - 1] + i * cnt[i];
     }
    console.log(dp[0][100000]);
})

题目内容

曾经有一个小镇，那里有一位叫做小红的年轻人。他拥有一种非常特别的技能，能够通过操作数组来获得最大的收益。

小红的技能最初得到了村里的某位老者的传授。老者告诉他，每次操作可以删除一个数 $arr_i$ ，同时删除所有等于 $arr_i+ 1$ 或者 $arr_i - 1$的数。操作后被删除的数无法再被选中。每次操作可以获得被删除数的分数，现在他想知道通过多次操作，他最多能够获得多少分。

为了帮助小红，老者给了他一个长度为 $n$ 的数组 $arr$，并告诉他最优的操作策略是什么。现在，小红需要你的帮助来解决这个问题。

输入描述

第一行一个正整数 $n$ ,表示数组 $arr$ 的长度。

接下来行包含 $n$ 个正整数 $arr_1, arr_2 ,...... arr_n$,分别为数组 $arr$ 中的 $n$ 个数。

$n\leq 100000,1\leq arr_i \leq100000$

输出描述

输出可以获得的最高分。

样例

样例一：

输入

5
1 2 3 4 5

输出

9

样例二：

输入

6
7 9 4 3 5 7

输出

31