Hello everyone !! It would be a great help if someone can explain the solution for the W problem. Thank You. Anyone please???????
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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.