Изменения

Требуется посчитать функцию $f(1, n)$. Принцип состоит в следующем: пусть на для всех отрезков $i$, $j$ (где <tex> u \le i \le j \le v </tex>) известен оптимальный ответ для функции $f(i, j)$. Тогда будем пересчитывать $f(u, v)$ через такие $f(i, j)$. Тогда мы будем вычислять $f(u, v)$ через такие $f(i, j)$. В качестве примера рассмотрим следующую классическую задачу: дана строка длины n, нужно найти максимальный подпалиндром (подпоследовательность максимальной длины, которая является палиндромом). Пусть $d(i, j)$ - ответ на задачу для подстроки, начинающаяся с символа $i$ и заканчивающаяся в символе $j$. Ясно, что $d(i, j) = 0$ для всех $i, j,$ что $i > j$ и $d(i, i) = 1$ для всех $i$. Пусть нам нужно посчитать значение для $d(i, j)$, причем значение $d$ для всех $l, r$, что <tex> i \le l \le r \le j </tex> уже посчитаны и они оптимальны. Рассмотрим два случая: <br />: 1) # <tex> s(i) \neq s(j), тогда d(i, j) = max/(d(i, j - 1), d(i + 1, j)) </tex> <br />: 2) # <tex> s(i) = s(j), тогда d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />Доказательство: (прим. мп - максимальный подпвлиндром) <br />1) # Так <tex>s(i) \neq s(j)</tex>, символы $s(i)$ и $s(j)$ не могут входит в мп максимальный подпвлиндром одновременно, то есть либо $s(i)$ входят в мп максимальный подпвлиндром (тогда его длина $d[i, j - 1]$), либо $s(j)$ входи в мп максимальный подпвлиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в мп максимальный подпвлиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br />2) # Данное равенство следует из факта, что выгодно включить в мп символы $s(i)$ и $s(j)$.