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

Автор Ragnar7, история, 4 года назад, По-английски

Hello everyone !! It would be a great help if someone can explain the solution for the W problem. Thank You. Anyone please???????

https://atcoder.jp/contests/dp/tasks/dp_w

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

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

Auto comment: topic has been updated by Ragnar7 (previous revision, new revision, compare).

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

    I have seen this , But he only explained a bit of what he is doing . I am not blaming but I was unable to understand this.

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

If you want to brute force this, let $$$dp_i$$$ denote the maximum score you can get if the last 1 you placed was at $$$i$$$. Now consider transitions from $$$dp_j$$$. it is $$$dp_i = max(dp_i, dp_j + s)$$$, where $$$s$$$ is the sum of all ranges such that $$$j<l$$$ and $$$i<r$$$. To maintain this information, we use a lazy segment tree that allows range increments and maximums. We iterate over $$$i$$$ from $$$1$$$ to $$$n$$$. When there is a range whose $$$l\le i$$$, we update the range $$$[0,l)$$$ with the value of the range, as those dp values will now have this range added to their $$$s$$$ value. When there is a range whose $$$r<i$$$, we undo the range update $$$[0,l)$$$ with $$$-val$$$, because this range no longer contributes to the $$$s$$$ value. We can implement this by sorting and 2 pointers.

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

    Thank you so much. It was hard to grasp at first but that DP transition made it really easy to digest. Thank you.