I was trying to solve the problem http://mirror.codeforces.com/problemset/problem/380/C .I saw Segment tree approach in the editorials.Now I was thinking Can we do it by memoization.Increasing the value +1 for every "(".Now we have two options ,Whether we should include next character to close this subsequence on not.Initially it would be exponential but by doing memoization I think we can do this.Looking to hear from you guyz?????
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 16.11.2024 11:22:27 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
I suggest you to take some time to fully understand about time complexity
How are you going to solve this problem using DP given those constraints? If you are going to just bruteforce on the query segment [l, r] it will take you O(n) per query giving you a O(mn) solution in the end. And talking about memoization, you are storing the answer for every [l, r] segment, which ends up using O(n2) memory and time complexity, by the end of the day you just get a O(mn2) solution (even worse than bruteforce xD)