[C/C++] Codeforce 455A - Boredom (DP)

A. Boredom

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it a k) and delete it, at that all elements equal to a k + 1 and a k - 1 also must be deleted from the sequence. That step brings a k points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input

The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence.

The second line contains n integers a 1, a 2, ..., a n (1 ≤ a i ≤ 105).

Output

Print a single integer — the maximum number of points that Alex can earn.

 

 

문제를 풀이하자면 만약 입력의 값이

11

1 3 2 5 4 1 1 4 5 2 5

처럼 주어졌다면 아래의 표와 같이 정리할 수 있다.

숫자	1	2	3	4	5
갯수	3	2	1	2	3

예를들어서 위의 표에서 4를 선택한다면 포인트는 4 x 2 = 8 만큼 얻을 수 있지만 동시에 3과 5는 쓸 수 없게 된다.

a[ ]라는 배열은 각 숫자의 갯수를 저장하는 배열이고, DP[ ]라는 배열은 DP[i] = i~N까지의 값들을 통해 만들 수 있는 점수의 최대값이라고 정의하자. 우리가 구해야 할 답은 DP[1] = 1~N까지의 값들을 통해 만들 수 있는 점수의 최대값이다.

i번째 DP값은 숫자 i를 고를 시 a[i+1]은 사용할 수 없으므로 a[i]*i + DP[i+2]이고

i+1을 고를 시 a[i+2]은 사용할 수 없으므로 a[i+1]*(i+1) + DP[i+3] 이며 DP[i]는 이 두 값중 큰 값으로 저장된다.

 

1) DP[5] = max(DP[7] + a[5] * 5, DP[8] + a[6] * 6);
2) DP[4] = max(DP[6] + a[4] * 4, DP[7] + a[5] * 5);
3) DP[3] = max(DP[5] + a[3] * 3, DP[6] + a[4] * 4);
4) DP[2] = max(DP[4] + a[2] * 2, DP[5] + a[3] * 3);
5) DP[1] = max(DP[3] + a[1] * 1, DP[4] + a[2] * 2);

 

<코드>

#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;

ll a[100010];
ll DP[100010];

int main(void)
{
	int x, N;

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &x);
		a[x]++;
	}

	for (int i = 100000; i >= 1; i--)
	{
		DP[i] = max(DP[i + 2] + a[i] * i, DP[i + 3] + a[i + 1] * (i + 1));
		
	}

	printf("%lld", DP[1]);

}

 

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

Problem - A - Codeforces