题目大意:给定一个序列,每次从序列中选中一个数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;
}