拿数问题

问题描述

给一个序列，里边有 n 个数，每一步能拿走一个数，比如拿第 i 个数， Ai = x，得到相应的分数 x，但拿掉这个 Ai 后，x+1 和 x-1 (如果有 Aj = x+1 或 Aj = x-1 存在) 就会变得不可拿（但是有 Aj = x 的话可以继续拿这个 x）。求最大分数。

Input

第一行包含一个整数 n (1 ≤ n ≤ 10^5)，表示数字里的元素的个数
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 10^5)

Output

输出一个整数：n 你能得到最大分值。

Sample

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

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

若分 x 拿了，则 x-1 跟 x+1 不可拿，但若有多个 x，则这些 x 都可拿。因此输入的时候可以对 x 分进行计数，若 x 拿了则全拿可以使分最大，同时记输入的最大数 max_x。

从 0 开始到 max_x，score[i] = max(score[i - 1], score[i - 2] + i * count[i])，即对于数 i，拿或不拿取决于 i - 2 与 i 拿了是否可以比 i - 1 大。

源代码

#include <iostream>
#include <algorithm>
#include <memory>
using namespace std;

const int maxSize = 100010;

long long Count[maxSize] = { 0 };
long long Score[maxSize] = { 0 };

int main() {
	int n;
	cin >> n;
	int maxN = -1;

	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		Count[a]++;
		maxN = max(maxN, a);
	}
	Score[1] = Count[1];
	for (int i = 2; i <= maxN; i++)
		Score[i] = max(Score[i - 1], Score[i - 2] + i * Count[i]);
	cout << Score[maxN] << endl;

	return 0;
}