302361: CF455A. Boredom
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Boredom
题意翻译
题目描述 亚力克斯不喜欢无聊。 所以每当他感到无聊他就会想出一些游戏。一个冬天的晚上他想出了一个游戏并且决定开始玩这个游戏。 给定一个有 $n$ 个元素的序列 $\{a_n\}$。你可以做若干次操作。在一次操作中我们可以取出一个数(假设他为 $x$)并删除它,同时删除所有的序列中值为 $x+1$ 和 $x-1$ 的数。这一步操作会给玩家加上 $x$ 分。 输入输出格式 输入格式 第一行一个整数 $n(1\le n\le 10^5)$,说明这个序列有多少数。 第二行 $n$ 个整数,分别表示 $a_1,a_2,\cdots,a_n$。 输出格式 一个整数,表示玩家最多能获得多少分 说明: 对于样例 4,第一步我们取 2,序列变为 [2,2,2,2]。接下来每一步都取 2,最后获得 10 分。题目描述
Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. Given a sequence $ a $ consisting of $ n $ integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it $ a_{k} $ ) and delete it, at that all elements equal to $ a_{k}+1 $ and $ a_{k}-1 $ also must be deleted from the sequence. That step brings $ a_{k} $ points to the player. Alex is a perfectionist, so he decided to get as many points as possible. Help him.输入输出格式
输入格式
The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ) that shows how many numbers are in Alex's sequence. The second line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ).
输出格式
Print a single integer — the maximum number of points that Alex can earn.
输入输出样例
输入样例 #1
2
1 2
输出样例 #1
2
输入样例 #2
3
1 2 3
输出样例 #2
4
输入样例 #3
9
1 2 1 3 2 2 2 2 3
输出样例 #3
10