Hello everyone !! It would be a great help if someone can explain the solution for the W problem. Thank You. Anyone please???????
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello everyone !! It would be a great help if someone can explain the solution for the W problem. Thank You. Anyone please???????
Название |
---|
Auto comment: topic has been updated by Ragnar7 (previous revision, new revision, compare).
Check this out https://youtu.be/FAQxdm0bTaw
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.
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.
Thank you so much. It was hard to grasp at first but that DP transition made it really easy to digest. Thank you.