【题解】CF455A Boredom

用 $f_i$ 表示删去所有元素 $i$ 之后的分数最大值。

1. 显然，若不删除大小为 $i$ 的元素，其分数就等于 $f_{i - 1}$。
2. 若删除大小为 $i$ 的元素，那么此时大小为 $i - 1$ 的元素就不能删除，因此此时分数等于 $f_{i - 2}$ 加上删去大小为 $i$ 的元素的分数。

综上，我们可以得到状态转移方程：

$$f_i = \max(f_{i - 1}, f_{i - 2} + cnt_i \times i) $$

$\texttt{Q}$ ：若删除大小为 $i$ 的元素，则大小为 $i+1$ 的元素就不能选了，为什么题解中没有涉及到这一点？

$\texttt{A}$：在对 $i+1$ 进行操作时，若执行操作 $1$，则没有选择 $i+1$，若执行操作 $2$，则我们用的是 $f_{i - 2}$ 加上新产生的分数而非 $f_{i - 1}$，因此不受影响。

$\text{AC Code}$：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 100005
int n;
int cnt[maxn], f[maxn];
int mmin = 1e9, mmax = -1e9;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x, cnt[x]++;
		mmin = min(mmin, x), mmax = max(mmax, x);
	}
	f[mmin] = cnt[mmin] * mmin;
	for(int i = mmin; i <= mmax; i++) 
		f[i] = max(f[i - 1], f[i - 2] + cnt[i] * i);
	cout << f[mmax];
	return 0;
}

题目大意

• 给定长度为 $n$ 的序列 $a$。

• 每次操作可以从序列中选出一个数 $x$，然后删除它以及序列中所有的 $x-1$ 和 $x+1$，并且获得 $x$ 分。

• 求出可以获得分数的最大值。

• $1\leq n,\ a_i\leq 10^5$

解题思路

为了让分数最大化，必然选择删光所有数才结束操作。

从序列 $a$ 中删除 $x$ 后，所有的 $x-1$ 和 $x+1$ 也被删除，故 $x$ 只能被作为选出的数删除。

容易想到用桶统计每个数出现的次数 $t_x$。

接着考虑动态规划。定义 $f_i$ 表示对于小于等于 $i$ 的数，可以获得的最大分数。对于 $f_{i+1}$（$1\leq i$）：

• 由于不操作序列中所有的 $i+1$ 最多可以获得 $f_i$ 分，故应初始化成 $f_i$；

• 考虑一个一个删除序列中所有的 $i$，那么可以获得 $it_i$ 分，对于小于等于 $i-1$ 的数，最多又可以获得 $f_{i-1}$。

综上，$f_{i+1}=\max(f_i,f_{i-1}+it_i)$。最后答案为 $f_{1+\max_{i=1}^na_i}$。

时间复杂度 $\Theta(n+\max_{i=1}^na_i)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],tot[100002],maxn;
long long dp[100002];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),tot[a[i]]++,maxn=max(maxn,a[i]); 
    for(int i=2;i<=maxn+1;i++){
        dp[i]=dp[i-1];
        if(tot[i-1])
			dp[i]=max(dp[i],dp[i-2]+tot[i-1]*(long long)(i-1));
    }
    printf("%lld\n",dp[maxn+1]);
    return 0;
}