5550 取数（max）

经验值：2000

时间限制：1000毫秒

内存限制：128MB

庐阳区2020年信息学竞赛试题

 不许抄袭，一旦发现，直接清空经验！

题目描述 Description

盒子里面有N个球，每个球上都一个数。你每次可以取走一个球，这个球上的数是X，你就可以得到X的分值，若还有其他的球上的数值也是X，你可以将这些球一并取走， 但是同时就有限制:其他的球，若上面的数为X-1或X+1的话，就不能被取了，相当于这些球被剔除。求你能取得的最大分值。

输入描述 Input Description

第一行一个整数N。

第二行，N个整数，为球上的数值Xi.

输出描述 Output Description

一个整数， 意义如题所述。

样例输入 Sample Input

5 5 3 5 3 4

样例输出 Sample Output

16

数据范围及提示 Data Size & Hint

对于30%的数据：1<=N<=100,1<=Xi<=100。
对于50%的数据：
1<=N<=10000,1<=Xi<=10000。
对于100%的数据：
1<=N<=1000000,1<=Xi<=1000000

#include<bits/stdc++.h>
using namespace std;
int n,x[10000005],t[10000005],mx;
long long dp[1000005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){cin>>x[i];t[x[i]]++;mx=max(mx,x[i]);
}
dp[0]=0,dp[1]=t[1];
for(int i=2;i<=mx;i++){dp[i]=max(dp[i-2]+i*t[i],dp[i-1]);
}
cout<<dp[mx];
return 0;
}