vsanjay_nitdgp's blog

dynamic programming
By vsanjay_nitdgp, history, 9 years ago, In English

Hello...I am a dream coder...and now I want to master dynamic programming...recently I solving the following problem....but couldn't understand the editorial.

Could any one pls explain this problem clearly..for a DP beginner.....

Thanks in advance

http://codeforces.net/contest/455/problem/A

Tags dp
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Let f[i] be the maximum sum he can get from taking only values less than or equal i. Then clearly f[0] = 0 since he can't take any of the aray elements. For other values of i, there are two possible cases. The first case is that he does not take any values from the array that are equal to i (sometimes it is better to not take them so he doesn't have to delete all occurrences of i+1 and i-1). In this case, f[i] = f[i-1]. If he doesn't take any values equal to i, the maximum sum he gets is no different than the maximum sum when he was only allowed to take values up to i-1. The other case is that he does take all occurrences of the value i (it's never optimal to take some but not all occurrences since he has to delete the other elements either way). In this case, he is not allowed to take any occurrences of i-1 since he has to delete them all, but he does get the benefit of adding i * freq[i] to his score (where freq[i] is the number of occurrences of i in the array). The fact that he has to delete all occurrences of i+1 will be taken care of when calculating f[i] so you don't have to worry about that. So in this case f[i] = i * freq[i] + f[i-2]. So when figuring out f[i], you take whichever of these cases results in a higher result. Here is some pseudo-code (assuming you pre-computed freq[i] for all i up to 100,000):

f[0] = 0;
for(int i = 1; i<=100000; i++)
{
f[i] = f[i-1];
if(i > 1) f[i] = Math.max(f[i], f[i-2] + i*freq[i]); // Watch out for overflow here.
}

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sir...how will I+1 be taken care byf(I)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The recurrence I think it's like this: 

      F(i) = max(F(i+2) * cnt[i] * i, F(i+1) );

base case: 

F(maxValueInInput+1) = 0, F(maxValueInInput+2) = 0;

      So you can take the i items and move to i+2 because the i+1 will be removed, or you will not take the i items and move to try i+1 :) I hope it helps!

      → Reply