codeforces _ 455A _ A. Boredom

https://codeforces.com/problemset/problem/455/A

Problem - 455A - Codeforces

풀이방법

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;
}

---

후기