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;
}