dp解Codeforces Round #260 (Div. 2)C. Boredom

#include<iostream>

#include<map>

#include<string>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

long long shu[100010],fu[100010];

int main()

{

	int t,n,i,r=-1,l=100010;

	cin>>n;

	for(i=0;i<n;i++)

	{

		cin>>t;

		shu[t]++;

		l=min(l,t);

		r=max(r,t);

	}

	fu[1]=1*shu[1];

	for(i=max(l,2);i<=r;i++)

		fu[i]=max(fu[i-1],fu[i-2]+shu[i]*i);

	//前i个数（包含i）所能得到的最大分数等于，前i-1个数所能得到的最大分数。和选择第i个数所能得到的最大分数

	//它们俩的最大值

	cout<<fu[r];

}