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

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

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

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    БЛАГОДАРЮ

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    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];
    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          → Ответить