拿数问题

拿数问题

发布于 2023-03-09 | 分类于动态规划、 oi | 2分钟 | 234字数 | 浏览量：

题目描述

给定 $n$ 个数，我们要从中选出多若干个数，其中任意大小不同的两数差的绝对值不能为 $1$ ，那么选出的数之和最大是多少。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数， $a_1,a_2 ,...,a_n$ ，表示这 $n$ 个数

输出格式

一个整数，选出的数的和的最大值

测试样例

样例输入

5
1 1 3 2 3

样例输出

数据规模

对于 $100 \%$ 的数据， $1 \le n \le 10^6, 1 \le a_i \le 10^6$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000002
ll dp[N], cnt[N], n, t;

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &t), ++cnt[t];
    dp[1] = cnt[1];
    for (int i = 2; i < N; ++i)
        dp[i] = max(dp[i - 1], cnt[i] * i + dp[i - 2]);
    cout << dp[N - 1];
}