| # | User | Rating |
|---|---|---|
| 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 |
| # | 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 |
Some Interval DP Problems and State Reduction
Hi everyone! Recently I have been solving some classic interval DP problems, and came across some neat problems. Most of these problems have relatively simple recurrence relations, but the straightforward solutions will not pass in complexity, hence requires an observation to reduce the complexity (generally by reducing the number of states by some pre-computation).
Prerequisites : Introductory interval DP such as Longest Increasing Subsequence, Longest Common Subsequence.
| Rev. | Lang. | By | When | Δ | Comment | |
|---|---|---|---|---|---|---|
| en50 |
|
lelbaba | 2022-11-10 16:10:07 | 1209 | (published) | |
| en49 |
|
lelbaba | 2022-11-10 15:01:42 | 2223 | ||
| en48 |
|
lelbaba | 2022-11-10 12:54:16 | 22 | ||
| en47 |
|
lelbaba | 2022-11-10 12:49:56 | 3580 | ||
| en46 |
|
lelbaba | 2022-11-10 12:26:40 | 14 | ||
| en45 |
|
lelbaba | 2022-11-10 12:22:40 | 36 | ||
| en44 |
|
lelbaba | 2022-11-10 12:18:22 | 20 | ||
| en43 |
|
lelbaba | 2022-11-10 12:16:59 | 881 | ||
| en42 |
|
lelbaba | 2022-11-10 12:14:13 | 1357 | ||
| en41 |
|
lelbaba | 2022-11-10 10:57:02 | 1313 | ||
| en40 |
|
lelbaba | 2022-11-08 16:11:57 | 4 | ||
| en39 |
|
lelbaba | 2022-11-08 16:11:22 | 1314 | ||
| en38 |
|
lelbaba | 2022-11-08 15:27:56 | 221 | ||
| en37 |
|
lelbaba | 2022-11-08 15:20:41 | 71 | ||
| en36 |
|
lelbaba | 2022-11-08 15:13:23 | 11 | ||
| en35 |
|
lelbaba | 2022-11-08 15:12:32 | 1262 | ||
| en34 |
|
lelbaba | 2022-11-08 14:45:23 | 777 | ||
| en33 |
|
lelbaba | 2022-11-08 14:18:25 | 70 | ||
| en32 |
|
lelbaba | 2022-11-08 14:16:32 | 49 | ||
| en31 |
|
lelbaba | 2022-11-08 14:13:37 | 121 | ||
| en30 |
|
lelbaba | 2022-11-08 14:11:03 | 188 | ||
| en29 |
|
lelbaba | 2022-11-08 13:58:38 | 58 | ||
| en28 |
|
lelbaba | 2022-11-08 13:57:19 | 5 | Tiny change: '$f_{i,j,k} denote wh' -> '$f_{i,j,k}$ denote wh' | |
| en27 |
|
lelbaba | 2022-11-08 13:56:26 | 921 | ||
| en26 |
|
lelbaba | 2022-11-08 11:12:27 | 2 | Tiny change: 'elation,\n\n$f_{l,l}' -> 'elation,\n$f_{l,l}' | |
| en25 |
|
lelbaba | 2022-11-08 11:11:52 | 2 | Tiny change: 'elation,\n$f_{l,l}' -> 'elation,\n\n$f_{l,l}' | |
| en24 |
|
lelbaba | 2022-11-08 11:10:41 | 4 | Tiny change: 'elation,\n\n$f_{l,l} = a_l$\n\n$f_{l,r}' -> 'elation,\n$f_{l,l} = a_l$\n$f_{l,r}' | |
| en23 |
|
lelbaba | 2022-11-08 11:09:46 | 4 | ||
| en22 |
|
lelbaba | 2022-11-08 11:09:08 | 5 | ||
| en21 |
|
lelbaba | 2022-11-08 11:07:39 | 4 | ||
| en20 |
|
lelbaba | 2022-11-08 11:05:47 | 1 | Tiny change: 'rations.\n\n<spoiler' -> 'rations.\n<spoiler' | |
| en19 |
|
lelbaba | 2022-11-08 11:04:51 | 2 | Tiny change: 'i} + 1)$\nNote: $[' -> 'i} + 1)$\n\nNote: $[' | |
| en18 |
|
lelbaba | 2022-11-08 11:03:12 | 22 | Tiny change: 'dp_1 = 1.$\n</spoile' -> 'dp_1 = 1.$ $dp_n$ is our answer.\n</spoile' | |
| en17 |
|
lelbaba | 2022-11-08 11:01:56 | 18 | Tiny change: '+ f_{j,i}$\n</spoil' -> '+ f_{j,i}$ where $dp_1 = 1.$\n</spoil' | |
| en16 |
|
lelbaba | 2022-11-08 10:59:52 | 2 | Tiny change: 'j \leq i, f_{j,i} \' -> 'j \leq i, \ f_{j,i} \' | |
| en15 |
|
lelbaba | 2022-11-08 10:59:09 | 4 | Tiny change: 'i} \ne 0} dp_{j-1} ' -> 'i} \ne 0} \ \ dp_{j-1} ' | |
| en14 |
|
lelbaba | 2022-11-08 10:58:27 | 237 | ||
| en13 |
|
lelbaba | 2022-11-08 10:41:39 | 4 | Tiny change: 'relation, //\n$f_{l,l}' -> 'relation, \\\n$f_{l,l}' | |
| en12 |
|
lelbaba | 2022-11-08 10:41:09 | 76 | ||
| en11 |
|
lelbaba | 2022-11-08 10:38:21 | 2 | Tiny change: '{l,i} + 1)\n</spoile' -> '{l,i} + 1)$\n</spoile' | |
| en10 |
|
lelbaba | 2022-11-08 10:37:57 | 158 | ||
| en9 |
|
lelbaba | 2022-11-08 10:24:51 | 5 | ||
| en8 |
|
lelbaba | 2022-11-08 10:22:29 | 233 | ||
| en7 |
|
lelbaba | 2022-11-08 10:18:02 | 292 | ||
| en6 |
|
lelbaba | 2022-11-08 09:37:52 | 9 | Tiny change: 'ed to.\n\n#### Claim\nIf the s' -> 'ed to.\n\n**Claim**\nIf the s' | |
| en5 |
|
lelbaba | 2022-11-08 09:36:52 | 305 | ||
| en4 |
|
lelbaba | 2022-11-08 09:08:05 | 63 | ||
| en3 |
|
lelbaba | 2022-11-08 09:03:16 | 98 | ||
| en2 |
|
lelbaba | 2022-11-08 08:28:51 | 65 | ||
| en1 |
|
lelbaba | 2022-11-08 08:19:37 | 1038 | Initial revision (saved to drafts) |
