Изменения

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