A93773.相邻数清理
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给定一个长度为 n 的序列,其中第 i 个数为 ai。
你可以进行若干次选择操作:
- 如果你决定选择某个数值 x,你会一次性拿走序列中所有等于 x 的元素,得到的分数为 x× (序列中 x 出现的次数)。
- 与此同时,序列中所有等于 x−1 和 x+1 的元素会被清空(之后无法再选择它们对应的数值)。
你可以选择若干个不同的数值(每个数值至多选择一次),目标是让最后得到的总分数最大。请输出这个最大分数。
输入格式
第一行一个整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数,表示可以获得的最大总分数。
输入输出样例
输入#1
5 1 2 2 3 3
输出#1
7
说明/提示
1≤n≤2×105
1≤ai≤105
对于样例:
各数出现次数:1 有 1 次,2 有 2 次,3 有 2 次。
-
选择 2 的话:得分 =2×2=4,且 1 与 3 不能再选。
-
选择 1 与 3 的话:得分 =1×1+3×2=7。
最大为 7。