Boredom

题面翻译

题目描述

给定一个有 $n$ 个元素的序列 ${a_n}$。你可以做若干次操作。在一次操作中我们可以取出一个数（假设他为 $x$）并删除它，同时删除所有的序列中值为 $x+1$ 和 $x-1$ 的数。这一步操作会给玩家加上 $x$ 分。

输入输出格式

输入格式：第一行一个整数 $n(1\le n\le 10^5)$,说明这个序列有多少数。 第二行 $n$ 个整数，分别表示 $a_1,a_2,\cdots,a_n$。（$1 \le a_i \le 10^5$ ）

输出格式：一个整数，表示玩家最多能获得多少分。

说明： 对于样例 3，第一步我们取 $2$，序列变为 $[2,2,2,2]$。接下来每一步都取 $2$，最后获得 $10$ 分。

分析

观察数据范围可知， $a_i$ 并不是非常大，考虑从这一点入手解决问题。

观察发现序列的顺序并不重要，首先想到的是对序列排序。
进一步，可以统计每一个数字出现的次数。
注意到，有一个贪心的结论：

  • 如果取了一个数 $x$ 且这个数出现了不止一次，那么我们可以把出现的所有的 $x$ 都取光，这只会使得答案更优。

开一个桶统计每一个数出现的次数，从小到大枚举，设 $dp[i]$ 表示一定取了数字 $i$ 时所获得的最大分数，考虑如何转移：

  • 枚举上一个选择的位置加上当前分数，注意范围。

简单思考后发现枚举上一个选择的位置是没有必要的，只需要维护一个最大值 last枚举的时候直接更新可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;

int n, m, la, ans;

int tot[N], dp[N];

signed main(){
	
	cin >> n;
	for (int i = 1, x; i <= n; i++)
		cin >> x, tot[x]++, m = max(m, x);
	
	for (int i = 1; i <= m; i++){
		if (i >= 2)
			la = max(la, dp[i - 2]);

		dp[i] = max(dp[i], la + tot[i] * i);
		ans = max(dp[i], ans);
	}
	
	cout << ans;
	
	return 0;
}

Written with StackEdit中文版.