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

Помогите решить
Автор mamka, история, 9 лет назад, По-русски

Есть строка s (длина s<=1000) Требуется удалить несколько символов строки (возможно ноль) так, чтобы получилась строка максимальной длины и являлась палиндромом.

Вывести длину искомой строки и ее саму.

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

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

Где можно проверить?

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

    Dl.gsu.by -> олимпиады по информатики -> Гомельская гор.\2015\Школьная 1-11 кл, 7 октября\9 — 11 кл\8 — "Палиндром"

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

Динамика по подстрокам.

Если s[i] = s[j], то dp[i][j] = dp[i + 1][j - 1] + 1, иначе dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]), где dp[i][j] — это максимальное количество символов, которое можно оставить в подстроке с i-того по j-тый символ так, чтобы остался палиндром. Ответ — dp[0][n - 1].

→ Ответить