codeforces _ 455A _ A. Boredom
https://codeforces.com/problemset/problem/455/A
풀이방법
ak를 선택시 ak-1, ak+1은 선택 못한다는것을 유의해서 점화식을 짜야한다.
dp[i] = max( dp[i-1], dp[i-2] + cnt[i]+i )
전체코드
#include <iostream>
#include <algorithm>
using namespace std;
int n;
long long cnt[100002];
long long dp[100002];
void Input()
{
cin >> n;
int value;
for (int i = 0; i < n; i++)
{
cin >> value;
cnt[value]++;
}
}
int main()
{
Input();
dp[0] = 0;
dp[1] = cnt[1] * 1;
for (int i = 2; i <= 100000; i++)
{
dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i] * i);
}
cout << dp[100000];
return 0;
}