Boredom Problem Solution - Codeforces 445A (Round 260, Div1)

This is a beautiful beginner level dynamic programming problem, and is quite important if you are just beginning to understand recursion.

Problem Statement - 

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 ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player. Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Problem Source - Codeforces 445A

Let's consider a simple case to begin with, if the sequence is 2 2 2. Then, clearly, Alex has only one choice - to pick the number 2. In that case, his score would be 2*3 = 6.

Moving forward, if the sequence was 2 2 3. Then Alex has two choices - to choose 2, or 3. Now, on choosing 2, his score would be 2*2 = 4. But (2 + 1) = 3 would be eliminated from the sequence, so 4 will be his final score. On the other hand, if he chooses 3, his score would be 3*1 = 3, and yet again, (3 - 1) = 2 will be eliminated from the array. Clearly, the maximal score is 4.

As it is clearly visible, it is the frequency of the number appearing, as well as the number itself that is significant. Hence, we initiate an array, count[i], storing the number of times the element i appears in the sequence.

Hence for the above sequence 2 2 3, count[2] = 2, and count[3] = 3.

Finally, to find the optimal score, it would be easy to first break the problem down into smaller problem. In this case, we break the sequence into smaller sequence and find optimal solution for it.

For the sequence of number containing only 0, the answer would be 0. Similarly, if a sequence contains only the number 0 and 1, then the solution would be count[1]*1.

Now we are ready to build the recursive solution for this problem. For a sequence of number containing only the numbers, 0 to n, we can either pick the nth element, or not. Hence,

dp[i] = 
max(
dp[i - 1], // Not picking the ith number, then the number before it can be considered
dp[i - 2] + i*a[i] // Picking the ith number, then the number before it is eliminated, hence the number before that is considered
);

Once we have the recursive solution, it is quite easy to see, that for the complete sequence of numbers, ie, from 0 to 100000, the solution is simply, dp[100000].

Hence the final code for the problem is -

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

long long int a[100007], n;
long long int dp[100007];

int main() {
    memset(a, 0, sizeof(a));
    cin >> n;
    for (int i = 0; i < n; i++) {
        int j;
        cin >> j;
        a[j]++;
    }
    dp[0] = 0;
    dp[1] = a[1]; // a[1]*1 = a[1]
    for (int i = 2; i <= 100000; i++) { // Finding optimal points until the ith number
        dp[i] = max(dp[i - 1], dp[i - 2] + i*a[i]);
    }
    cout << dp[100000];
    return 0;
}