I was trying to solve the problem http://codeforces.me/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?????
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 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 |
| 9 | nor | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/24/2024 08:54:14 (i2).
Desktop version, switch to mobile version.
Supported by
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)