Олимпиады по программированию

www.olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 02-1. Минимальный путь в таблице.
(Разбор)

Будем решать более общую задачу (что, как ни странно, зачастую оказывается проще), а именно найдем цену b_i,j минимального пути из правой верхней клетки в клетку (i,j). Заметим, что попасть в клетку (i,j) мы могли только из клеток (i-1,j) и (i,j-1). Значит, задачу можно свести к решению подзадач для клеток (i-1,j) и (i,j-1).

Результаты решения подзадач удобно хранить в таблице b размером NxM. Тогда b_i,j=min(b_i-1,j,b_i,j-1)+a_i,j ( здесь a - таблица из условия). Применить эту формулу не составляет труда, если b_i-1,j и b_i,j-1 уже посчитаны. А это легко достигается, если заполнять таблицу b слева направо сверху вниз (т.е. сначала слева направо заполняется первая строка, затем вторая и т.д.). Заметим, что для первой строки и первого столбца формула работает плохо, т.к. там появляются несуществующие элементы таблицы. Их можно заполнить в самом начале, поскольку в каждую из этих клеток можно попасть только одним способом. Ответ на поставленную задачу будет находиться в правом нижнем углу таблицы b.

Количество действий, выполненных этим алгоритмом, пропорционально числу клеток в таблице.