Помощь - Codeforces

Блог пользователя chinese

Помощь

Автор chinese, история, 8 лет назад, По-русски

Помогите с задачей : Тык

Придумал динамику за N ^ 5, но она не проходит по TL

chinese
8 лет назад
7

Комментарии (7)

Написать комментарий?

MStrechen

8 лет назад, скрыть # |

Прежде всего, имеет смысл писать длинную арифметику или использовать 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]

→ Ответить

chinese

8 лет назад, скрыть # ^ |

БЛАГОДАРЮ

→ Ответить

chinese

8 лет назад, скрыть # ^ |

что то не выходит(( Можешь помочь??

dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= n; j++) 
			if(s[i] == '(' && j) dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1];
			else if(s[i] == ')') dp[i][j] += dp[i - 1][j] + dp[i - 1][j + 1];
	cout << dp[n][0];

→ Ответить

MStrechen

8 лет назад, скрыть # ^ |

При j = 0 dp[i-1][j-1] — непонятно что (выход за границы массива) В s первый символ — какой? В плане, учитывается ли то, что s должна нумероваться с единицы? Можно в этом месте написать просто s[i - 1] и не заморачиваться. И реализована ли длинная арифметика? Ответ в этой задаче может превосходить 2^63 во много раз.

→ Ответить

chinese

8 лет назад, скрыть # ^ |

s начинается с 1, когда j = 0 учел(if(s[i] == '(' && j)), на тесте ((())())( не работает

→ Ответить

MStrechen

8 лет назад, скрыть # ^ |

← Rev. 2 →

Прошу прощения, неверно понял условие задачи. Думал, что нужно найти именно количество различных подпоследовательностей.

Я почему-то не могу найти разбор конкретно этой задачи, но ключевая идея такова: 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 был разбор этой задачи, однако я его сходу найти не могу, к сожалению.

→ Ответить