NC214364. 小游戏
描述
输入描述
第一行一个整数 n. ( 1 ≤ n ≤ 2e5)
第二行 n 个整数 a[i]. (0 ≤ a[i] ≤ 2e5)
输出描述
输出能得到的最大分数。
示例1
输入:
5 1 2 2 2 3
输出:
6
说明:
拿走 3 个 2示例2
输入:
3 1 2 3
输出:
4
说明:
拿走 1 和 3C++(clang++11) 解法, 执行用时: 61ms, 内存消耗: 4728K, 提交时间: 2021-02-28 21:23:48
#include <iostream>
using namespace std;
long long a[200005],dp[200005];
int main() {
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
a[x]+=x;
}
for(int i=1;i<=200000;i++)
dp[i]=max(dp[i-1],dp[max(0,i-2)]+a[i]);
cout << dp[200000];
return 0;
}