Изменения

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