CSU-ACM2017暑期训练8-动态规划初步 F - Boredom

F - Boredom

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.

Example

Input 2 1 2 Output 2 Input 3 1 2 3 Output 4 Input 9 1 2 1 3 2 2 2 2 3 Output 10

Note

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.

由于被删除的元素只与被取出的元素的值有关，所以输入的序列是没有顺序的，只需要考虑每个元素的值是否被选中。

假设有一个足够长的序列，从中取出5，那么4和6就不会被考虑；小于4，和大于6的值则不受影响。 一般情况：从最小数字开始考虑，设当前考虑的数字为 x ，①假定它是因 x−1 被计入分数而被忽略的，②或者它是要被计入分数的。对于情况①， x 被忽略了，所以在考虑 x 时，最高得分就等于考虑 x−1 时的最高得分；对于情况②， x 被计入分数，故 x−1 被忽略，这时最高分数等于 x−2 时的最高分数加上 x 对应的分数。根据这些描述得到状态转移方程： dp[i]=max{dp[i−2] pts,dp[i−1]} 其中 pts 为情况②中的 x <script type="math/tex" id="MathJax-Element-12">x</script> 对应的分数。

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int maxn = 1e5+4; long long n, maxNum; long long occurrence[maxn], sample, dp[maxn]; //数组occurrence[]是对输入的样例进行桶排序用的 int main(){ #ifdef TEST freopen("test.txt", "r", stdin); #endif // TEST while(cin >> n){ memset(occurrence, 0, sizeof(occurrence)); memset(dp, 0, sizeof(dp)); maxNum = 0; for(int i = 1; i <= n; i++){ scanf("%lld", &sample); occurrence[sample]++; if(sample > maxNum) maxNum = sample; } dp[1] = occurrence[1]; for(int i = 2; i <= maxNum; i++){ long long pts = i*occurrence[i]; dp[i] = max(dp[i-2]+pts, dp[i-1]); } cout << dp[maxNum] << endl; } return 0; }