Изменения

Требуется посчитать функцию $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)$. Пусть вершины пронумерованы в порядке топологической сортировки через такие $wf(i, j)$ - величина ребра от $i$ до $j$. В качестве примера рассмотрим следующую классическую задачу: дана строка длины n, нужно найти максимальный подпалиндром (если ребра не существуетподпоследовательность максимальной длины, то данное значение равно $\infty$которая является палиндромом) и . Пусть $d(i, j)$ - ответ на задачудля подстроки, начинающаяся с символа $i$ и заканчивающаяся в символе $j$. Ясно, что $d(i, ij) = 0$. Путь от вершины для всех $i, j,$ до что $i > j$ пересчитывается следующим образом: пусть и $d(i, i) = 1$ для любого всех $ki$ . Пусть нам нужно посчитать значение для $d(k = [i.., j])$, причем значение $d(i$ для всех $l, k)r$ и $d(k, что <tex> i \le l \le r \le j)$ </tex> уже посчитаны, тогдаи они оптимальны. Рассмотрим два случая: <br />: 1) <tex> s(i) \neq s(j), тогда d(i, j) = \minmax/(wd(i, j- 1), \min\limits_{\mathop{kd(i + 1, j)) </tex> <br />:2) <tex> s(i \rightsquigarrow k \rightsquigarrow ) = s(j}} [), тогда d(i, kj) + = d(ki + 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(uj)$ входи в мп (тогда его длина $d[i + 1, vj]$), либо оба не входят в мп (тогда его длина $= d[i, j - 1] = d[i + 1, j]$).<br />2) Данное равенство следует из факта, что выгодно включить в мп символы $s(i)$ и $s(j)$.