harshit2202's blog

Another DP Problem
By harshit2202, history, 7 years ago, In English

Problem Statement

Unable to solve the problem Editorial is also not available . Can anybody explain? Thanks in advance:)

Tags #dp
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Store an array b where b[i] is the sum of all aj = i

So in the sample, b would be {2, 10, 6}, the problem turns into a simple DP problem, if you are at state i you have 2 options:

1) leave b[i] and move to state i + 1

2) take b[i] and move to state i + R + 1

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

    Giving WA:(

    It will be wrong for test case 1 2 1 2 1 3

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Sorry missed one more thing, you should set R = min(L, R)

      because if you start taking elements in increasing order, then the difference between every consecutive values should be at least R

      and if you start taking elements in decreasing order, then the difference between every two consecutive values should be at least L

      The optimal solution is to choose the order which gives the minimum difference between consecutive values which is min(L, R)

      code

      → Reply