Cf 455A [Boredom]

Cf 455A Boredom

题意:

给出 \(n\) 个数字，从中选一个 \(a_k\) 删除，\(a_k\) 为你获得的值，删除 \(a_k\) 后，如果数组里面有\(a_{k + 1},a_{k - 1}\) 也会被删除，求获得值最大为多少?

数据范围:

\(n \le 1e5\)

思路:

设状态为 \(f[i]:\) 到达第 \(i\) 个点当前获得的最大值，虽然当前选会影响到后面，但是转移的时候，还是基于第 \(i\) 个点思考，不用考虑第 \(i + 1\) 个点。

转移方程: \(f[i] = max(f[i - 1],f[i - 2] + a[i])\)

实现:

#include <stdio.h>
#include <algorithm>
using namespace std;
long long arr[100005];
int vis[100005] = {0};
long long dp[100005] = {0};
int main()
{
    long long n;
    scanf("%lld", &n);
    long long r = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
        vis[arr[i]]++;
        r = max(r, arr[i]);
    }
    dp[1] = vis[1];
    for (int i = 2; i <= r; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + (long long)i * vis[i]);

    printf("%lld\n", dp[r]);
    return 0;
}