Codeforces 455A Boredom(高效)

题目链接：Codeforces 455A Boredom

题目大意：给定一个序列，每次从序列中选中一个数ak,获得ak的得分，同时删除序列中所有的ak−1,ak+1,求最大得分。

解题思路：开一个数组记录各个数有多少个，然后遍历一遍 ，维护两个值，一个是前一个不选的最大值，一个是前一个选的最大值。hack点，爆int了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 1e5+5;

int n, arr, c[maxn];

int main () {
    cin >> n;
    memset(c, 0, sizeof(c));

    for (int i = 0; i < n; i++) {
        cin >> arr;
        c[arr]++;
    }

    ll p = 0, q = 0;

    for (int i = 1; i < maxn; i++) {

        ll tmp = q + 1LL * i * c[i];
        q = max(p, q);
        p = tmp;
    }

    cout << max(p, q) << endl;
    return 0;
}