Гра з рядком#150

Гра з рядком (Editorial)

У задачі йдеться про найдовший підпаліндром, тобто підпослідовність (символи не обов'язково поспіль), яка є паліндромом. Це класична задача динамічного програмування.

Для рядка довжини позначимо \mathrm{dp}[i][j] — довжину найдовшого підпаліндрому підрядка s_i \ldots s_j. Тоді

  • \mathrm{dp}[i][i] = 1;

  • якщо s_i = s_j, то крайні символи вигідно взяти обидва: \mathrm{dp}[i][j] = \mathrm{dp}[i+1][j-1] + 2;

  • інакше хоча б один із крайніх символів не входить у відповідь: \mathrm{dp}[i][j] = \max(\mathrm{dp}[i+1][j],\; \mathrm{dp}[i][j-1]).

Стани заповнюємо в порядку зростання довжини підрядка (або рекурсією з мемоізацією). Відповідь для всього рядка — .

Корисний альтернативний погляд: найдовший підпаліндром рядка — це найдовша спільна підпослідовність та оберненого .

У цій задачі запитів k \le 10, а довжина рядка не перевищує . Тому найпростіше на кожен запит вирізати підрядок s_l \ldots s_r і запустити для нього динаміку з нуля: це \mathcal{O}(k \cdot n^2), тобто щонайбільше 10^5 операцій.

Не забудьте, що індекси в умові нумеруються з одиниці.