第十周作业 C题

C 拿数问题

题目描述：

解题思路：构造一个元素值为数组下标，元素出现次数的一个新数组，之后遍历每个值score[i]=max(score[i-1],score[i-2]+i*b[i]);即可`

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100010;
long long a[maxn],b[maxn],score[maxn];
long long ans=0;
int main()
{
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]++; 
	}
	sort(a+1,a+n+1);
	for(long long i=a[1];i<=a[n];i++)
	{
		score[i]=max(score[i-1],score[i-2]+i*b[i]);
		ans=max(ans,score[i]);
	}
	cout<<ans<<endl;
	return 0;
 }