#1526. 徐老师的逃生游戏
-
ID: 1526
Type: Default
1000ms
256MiB
Tried: 1
Accepted: 1
Difficulty: 10
Uploaded By:
sulaoshi
Tags> 徐老师的逃生游戏
说明
徐老师某天一觉醒来，发现自己穿越到了一个逃生游戏中！历经重重困难，徐老师终于来到了最后一关面前，游戏倒计时还有最后的一分钟
徐老师只要能解开最后一个密码，就能成功逃生
这个游戏是这样的：给出一组 $n$ 个数字，玩家每次可以选择其中一个数字 $x$，删除所有 $x$ 并获得它们总和的得分，也就是如果有 $cnt$ 个 $x$，则这一次删除可以获得 $cnt * x$ 的得分，但同时，所有的 $x-1$ 和 $x + 1$ 也会被删除，这两个数字不得分，一直重复直到没有数字为止。
现在最后一关的密码就是这个游戏的最大得分，徐老师太累了，已经没有精力思考了，希望你能帮帮他。
输入格式
第一行包含一个整数 $n$,表示有 $n$ 个整数。第二行包含 $n$ 个整数，表示第i个数字值为 $a_i$，之间以一个空格隔开。
| 数据点编号 | n的范围 | $a_i$的范围 |
| :---: | :---: | :---: |
| $1 \sim 4$ | $1 \leq n \leq 10^3$ | $0 \leq a_i \leq 10^3$（保证每个 $a_i$ 独一无二） |
| $2 \sim 5$ | $1 \leq n \leq 10^3$ | $0 \leq a_i \leq 10^3$ |
| $6 \sim 10$ | $1 \leq n \leq 10^6$ | $0 \leq a_i \leq 10^6$ |
输出格式
输出一个整数，表示密码。样例
5
5 6 6 4 1127提示
1. 删除 $11$ 获得 $11$ 分，同时删除 $10$ 和 $12$，$[5,6,6,4,11] -> [5,6,6,4]$
2. 删除 $6$ 获得 $2 * 6=12$ 分，同时删除 $5$ 和 $7$，$[5,6,6,4] -> [4]$
3. 删除 $4$ 获得 $4$ 分
最终得分 $11 + 12 + 4 = 27$ 分