题目描述
Alex doesn’t like boredom. That’s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.
Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence （let’s denote it ak） and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.
Alex is a perfectionist, so he decided to get as many points as possible. Help him.
输入描述
The first line contains integer n $(1 ≤ n ≤ 10^5)$ that shows how many numbers are in Alex’s sequence.
The second line contains n integers $a_1, a_2, …, a_n$ $(1 ≤ a_i ≤ 10^5)$.
输出描述
Print a single integer — the maximum number of points that Alex can earn.
题意分析
没有
样例输入
2
1 2
样例输出
2
AC代码
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn=1e6+10;
const ll mod=1e9+7;
ll a[maxn],dp[maxn];
int main() {
IOS;
ll n,i,t=-1;
cin>>n;
for(i=0;i<n;i++){
ll x;
cin>>x;
a[x]++;
t=max(t,x);
}
ll ma;
dp[1]=a[1];
for(i=2;i<=t;i++){
dp[i]=max(dp[i-1],dp[i-2]+a[i]*i);
}
cout<<dp[t]<<endl;
}
