Блог пользователя harshit2202

Another DP Problem
Автор harshit2202, история, 6 лет назад, По-английски

Problem Statement

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

Теги #dp
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Giving WA:(

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks:) Got it.

        → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        hey mate can u explain why it should be min(l,r) and not max(l,r)?? update :-> i got it,still thanks!!

        → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It can be done with this way as well: do DP twice..from index 0 and going to right with distance R and from index 1e5 with distance L, then pick the maximum of the two values obtained.

        → Ответить