Изменения

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