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

How to solve this question using dp .

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

Problem- link

Please anybody explain the soln.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

see Ashishgup solution . dp cant be more neat than his solution

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

    I saw but unable to understand this single line means why everyone is using suffix array even if we are processing from left to right :(

    ans = max(dp(i + 1), a[i] + suf[i + 1] — dp(i + 1));

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

      My logic was:

      DP(i) stores the maximum value a particular player can get if he starts at the ith index and goes till the end of the array.

      One possibility is, I retain my turn and skip the element, thus going to dp(i+1).

      Other possibility is, I take the ith element (and get a score of a[i]) and lose my turn. If I lose my turn, then the score I get is:

      sum of remaining elements — the maximum score that the other player can get if he starts at index i + 1.

      That is, suf[i+1] — dp(i+1).

      Hence the line: ans = max(dp(i + 1), a[i] + suf[i + 1] — dp(i + 1)).

      → Ответить