Рядки в Ужляндiї#171

Рядки в Ужляндiї (Editorial)

Природна динаміка тут очевидна: нехай f_i — максимальна кількість балів, з якою можна дістатися позиції . Тоді

f_i = \max_{j < i} \Bigl( f_j + (i - j)\,|S_i - S_j| \Bigr),

а відповідь — f_N. Але прямо це \mathcal{O}(N^2), що завелико.

Рятує те, що літер лише . Розкриємо дужки:

f_j + (i-j)\,|S_i - S_j| \;=\; \underbrace{i \cdot |S_i - S_j|}_{\text{залежить від } i} \;+\; \underbrace{\bigl(f_j - j \cdot |S_i - S_j|\bigr)}_{\text{залежить від } j}.

Ключове спостереження: величина |S_i - S_j| залежить не від самих індексів, а лише від пари літер. Тому зафіксуємо пару , де — літера в позиції , а — літера в позиції , і позначимо d[c][\mathit{ch}] = |c - \mathit{ch}|.

Заведемо таблицю

b[c][\mathit{ch}] = \max_{j:\; S_j = c} \bigl(f_j - j \cdot d[c][\mathit{ch}]\bigr),

тобто найкращий «внесок» позиції з літерою , якщо ми стрибатимемо в позицію з літерою . Це всього 26 \times 26 чисел.

Тоді перехід стає швидким:

f_i = \max_{c} \Bigl( i \cdot d[c][S_i] + b[c][S_i] \Bigr),

тобто на позицію. Після обчислення f_i оновлюємо таблицю: для кожної літери покладемо

b[S_i][\mathit{ch}] \leftarrow \max\bigl(b[S_i][\mathit{ch}],\; f_i - i \cdot d[S_i][\mathit{ch}]\bigr).

База: f_1 = 0, і для першої позиції одразу заповнюємо відповідні клітинки таблиці; решту ініціалізуємо «мінус нескінченністю», щоб не стрибати з позицій, яких ще не було.

Складність — за часом і \mathcal{O}(26^2) за пам'яттю. Бали сягають порядку N \cdot 25 \cdot N, тобто до 10^{11} і більше, тому рахуйте у 64-бітному типі.