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

Помогите новичку с задачкой

Автор tamir, 12 лет назад, По-русски

Всем доброго дня ! Хотелось бы попросить вас о помощи в решении задачи ( 159D - Палиндромные пары) и объяснении решения. Разбора я не понял , коды других участников смотрел — результат тот же. В общем , помогите новичку ) Спасибо за внимание !

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

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Не знаю точно, пройдет или нет. Но по данным ограничениям должно.

  1. Для начала надо знать является ли подстрока от i до j палиндромом. Это можно хранить в dp[i][j], вычисляя методом ДП.
  2. Заведем второй массив d1[]. d1[i] будет хранить количество палиндромов оканчивающиеся i символом включительно.
  3. Третий массив d2[]. d2[i] будет хранить количество палиндромов начинающихся с символа j (j >= i).
  4. И последняя часть. Ответом будет следующее число:

s = d1[1]*d2[2] + d1[2]*d2[3] + ... + d1[n — 1]*d2[n]; Осталось лишь только реализовать, желаю удачи.

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

    4-ый пункт неверен, т.к. по условию необязательно, чтобы искомые пары граничили. Т.е. для d1[1] (пользуясь Вашими обозначениями) подходят не только d2[2], но и все d2[i], где i > 1. Поэтому ответ: сумма d1[i] * (d2[i + 1] + ... + d2[n]) по всем i от 1 до n — 1.

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

      Перечитайте 3-ий пункт.

      1. Третий массив d2[]. d2[i] будет хранить количество палиндромов начинающихся с символа j (j >= i).

      Хочу акцентировать внимание на:

      начинающихся с символа j (j >= i).

      Вопрос: Почему даже когда у меня верно, все равно всегда мои посты минусуют? По какой логике вобще ставятся + и -?

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

        Ну когда я был синим (то есть совсем недавно), меня тоже минусовали. ;)

        UPD: похоже, сейчас мало что изменилось

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

Ещё один способ: 1) Находишь все палиндромы за О(длина). (здесь описан этот способ) А дальше уже считаешь.

→ Ответить