Помогите с задачей : Тык
Придумал динамику за N ^ 5, но она не проходит по TL
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
| Название |
|---|



Прежде всего, имеет смысл писать длинную арифметику или использовать Python. Это так, дисклеймер
DP[i][bal]— количество способов получить подпоследовательность префикса длиной i с балансом ровно bal (если что, баланс — разница между количеством открывающих и закрывающих скобок, а у любого префикса правильной скобочной последовательности баланс неотрицательный).База —
DP[0][0] = 1, DP[0][i]для любого i положим равным0Переходы: Еслиs[i](нумеруя с 1 нашу исходную последовательность) — открывающая скобка, тоDP[i][bal] = DP[i - 1][bal] + DP[i - 1][bal - 1], иначеDP[i][bal] = DP[i][bal] + DP[i - 1][bal + 1]БЛАГОДАРЮ
что то не выходит(( Можешь помочь??
При
j = 0dp[i-1][j-1]— непонятно что (выход за границы массива) Вsпервый символ — какой? В плане, учитывается ли то, чтоsдолжна нумероваться с единицы? Можно в этом месте написать простоs[i - 1]и не заморачиваться. И реализована ли длинная арифметика? Ответ в этой задаче может превосходить 2^63 во много раз.s начинается с 1, когда j = 0 учел(if(s[i] == '(' && j)), на тесте ((())())( не работает
Прошу прощения, неверно понял условие задачи. Думал, что нужно найти именно количество различных подпоследовательностей.
Я почему-то не могу найти разбор конкретно этой задачи, но ключевая идея такова:
dp[pos][bal]— количество скобочных подпоследователньостей с балансомbal(баланс в данном случае мы считаем "наоборот", с конца в начало, находящихся вpos-том суффиксе строки (элементах pos, pos+1, ..., n) и начинающихся со скобки на позиции pos. Мы можем считатьdp[pos][bal], рассматривая толькоdp[p_open][bal + 1]иdp[p_close][bal - 1], гдеp_openиp_close— позиции следующих открывающей и закрывающей скобок (ближайших справа).Если кратко, ответ будет посчитан корректно, потому что если мы можем составить скобочную последовательность с определенным балансом, которая будет использовать символы из i-ого суффикса строки, то мы можем составить такую же скобочную последовательность и из символов j < i-ого суффикса строки. Из этого следует, что можно рассмотреть только наименьший.
Прошу прощения за ложную наводку :)
Вот код моего решения на С++ — https://repl.it/@MatthewStrechen/ACMP614
Где-то на англоязычном CodeForces был разбор этой задачи, однако я его сходу найти не могу, к сожалению.
спс огромное