Изменения

Требуется посчитать функцию f(1, n). Принцип состоит в том, что мы пересчитываем f(u, v) через такие f(i, j), что <math> u \le i \le j \le v </math>. Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер <math> \in Z </math>- любое вещественное число. Требуется найти кратчайший путь от каждой вершины u до каждойv. Пусть вершины пронумерованы в порядке топологической сортировки и 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\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} (d(i, k) + d(k, j)) </tex><br /> Ответ будет равен d(u, v).

=== Принцип оптимальности на подмножествах ===