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

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

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

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

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

»
14 лет назад, скрыть # |
← 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]; Осталось лишь только реализовать, желаю удачи.

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

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

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

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

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

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

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

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

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

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

→ Ответить