CF-455A Boredom 题解

题目大意

给你一个数组a，里面有n个整数。你每次可以选择数组中的一个元素ak，从数组中删掉它，再删掉所有值等于ak + 1 或者 ak - 1的元素，这样你可以得到 ak 分。你可以重复进行多次该操作，请问你最后最多能得多少分？

解题思路

每个数字都分为两种情况，选和不选。

（这样其实和01背包有点类似

这样我们可以用一个数组，储存每个数字的出现次数。

用DP的思想，令数组dp[i]为1~i的最大分数。

对于每一个数来说，分为两种情况

1、选这个数 那么i-1这个数就不能选，dp[i]=dp[i-2]+cnt[i]*i。

2、不选这个数 那么dp[i]=dp[i-1]。

得出状态转移方程dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i)。

答案为dp[n]。

（DP苦手啊。。

本来可以一遍过的。。

结果没考虑数据范围，卡了我半个多小时。。

一定要注意啊啊啊

完整代码

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

const int N = 1e5+5;
int cnt[N];
long long dp[N];

int main() {
	int n,m=-1e9;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		cnt[a]++;
		m = max(m, a);
	}
	dp[1] = cnt[1];
	for (long long i = 2; i <= m; i++) {
		dp[i] = max(dp[i - 2] + cnt[i] * i, dp[i - 1]);
	}
	cout << dp[m] << endl;
}