CodeForces 456-C Boredom

题目链接：CodeForces -456C

Description

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.

Input

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).

Output

Print a single integer — the maximum number of points that Alex can earn.

Sample Input

2

1 2

9

1 2 1 3 2 2 2 2 3

Sample Output

Hint

Consider the third test example. At first step we need to choose any element equal to 2. 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 to 2. In total we earn 10 points.

题意

给你一串数，作为一个游戏参与者，你需要选择把一些数拿走以获得最大的分数，但是你不可以拿相邻的数字，比如你拿了3就不能拿2和4但是可以拿5，当然为了拿到尽可能多的分数，选择一个数就要把这个数都拿完。

题解：

DP中的水题，在输入时进行计数，算出每个数有几个，然后从1开始，计算从1开始到n个数之间能拿到的最大分数，状态转移式是DP[n]=max(DP[n-1],DP[n-2]+a[n]*n),前2个需要手算，剩下的O（n)跑一遍就可以了。

代码



#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<cstring>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

const double PI = acos(-1.0);

const double eps = 1e-6;

const int INF = 0x3f3f3f3f;

const int N = 2e5 + 5;

long long a[100100];

long long dp[100100];

int main() {

	int n;

	long long t;

	while (cin >> n) {

		memset(a, 0, sizeof a);

		for (int i(0); i <n; i++) {

			cin >> t;

			a[t]++;

		}

		dp[1] = a[1] * 1;

		dp[2] = max(a[2] * 2, a[1]);

		for (int i(3); i < 100100; i++) {

			dp[i] = max(dp[i - 2] + a[i] * i, dp[i - 1]);

		}

		cout << dp[100099] << endl;

	}

	return 0;

}

巴特西