1 second
256 megabytes
standard input
standard output
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 itak) and delete it, at that all elements equal
toak + 1 andak - 1 also must be deleted from the sequence. That step bringsak
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 ≤ 105) that shows how many numbers are in Alex's sequence.
The second line contains n integers
a1, a2, ...,an (1 ≤ ai ≤ 105).
Print a single integer — the maximum number of points that Alex can earn.
2 1 2
2
3 1 2 3
4
9 1 2 1 3 2 2 2 2 3
10
Consider the third test example. At first step we need to choose any element equal to2. After that step our sequence looks like this
[2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to2. In total we earn
10 points.
显然每个数只有2个状态，被丢掉（相当于不选），选中后丢掉(相当于选）
所以决策过程就很明显了，dp[i]1]表示i这个数选中，那么既然他选了，i-1就不能选了，所以有dp[i][1] = dp[i-1][0] + num[i]*i;
dp[i][0] 表示被丢弃,那么i-1可选可不选，dp[i][0] = max(dp[i-1][1], dp[i-1][0])
大家可能会想，题目中说选了i，i-1,i+1都不能选，为什么可以单向推导dp呢，因为当我们计算i+1被选上时，用的是i没有被选上的情况，所以并不会影响，而计算i+1没被选上时，由于本身就没被选上了，那么i对它有无影响也就无所谓了
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
__int64 dp[N][2];
int main()
{
int n;
while (~scanf("%d", &n))
{
map<int, int> num;
num.clear();
int t, maxs = 0, mins = 0x3f3f3f3f;
for (int i = 0; i < n; i++)
{
scanf("%d", &t);
maxs = max(t, maxs);
mins = min(t, mins);
num[t]++;
}
memset ( dp, 0, sizeof(dp) );
for (int i = mins; i <= maxs; i++)
{
dp[i][1] = dp[i - 1][0] + (__int64)num[i] * i;
dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
}
printf("%I64d\n", max(dp[maxs][1], dp[maxs][0]));
}
return 0;
}