Изменения

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

Ответ будет равен $d(u, v)$.