Наибольший путь

Задача такая. Дана матрица n*n. Заполнена она значениями от 1-10. Найти путь при котором сумма
приоритета клеточек была наибольшей. И еще есть ограничение при продвижение:двигаться можно только вниз и вправо.
Минимальный бы путь ерунда алгоритм ветровой, так вроде его называют, а тут во че за фигня.
Люди подкиньте ка идейку по решению такой вот задачи. И еще где можно почитать решения такого рода задач или
закавыристые задачки, а то к олимпиаде надо подготовиться, все проги да проги писал, а тут вон че.
Заранее спасибо...

Если сюда выложить решение этой задачи, алгоритма не поймешь.. если ты хочешь к олимпиаде подготовиться. Метод решения - динамическое программирование.

ЗЫ. для "закавыристых" задачи есть только один метод решения : мозги + опыт.

Сообщение отредактировано: PropellerMan - 03.04.03, 16:41

Идея вот в чём:
Пусть клетки пронумерованы от [0,0] до [N-1,N-1]. Пусть мы стоим в клетке [I,J] и знаем, как попасть из клеток [I+1,J] и [I,J+1] самым длинным путём в клетку [N-1,N-1] а также стоимость этого пути.

Тогда самый длинный путь из клетки [I,J] в клетку [N-1,N-1] определяется, как самый длинный из двух путей - пути из [I,J] через [I+1,J] и пути через [I,J+1]. Если клетка расположена на правом или нижнем краю таблицы, то выбора нет. Стоимость пути из клетки [I,J] в угол таблицы расчитывается, как стоимость пути из [I,J] в соседнюю клетку A плюс стоимость пути из A в угол.

Для каждой клетки достаточно хранить стоимость самого длинного пути из неё и первую клетку на этом пути - направление первого шага в этом пути. Получаешь две матрицы - матрицу стоимостей путей и матрицу направлений. Если обходить клетки матрицы в порядке убывания суммы координат и проводить указанные вычисления, то в клетке [0,0] будет цена самого длинного пути и первый шаг на этом пути. И в каждой клетке матрицы будет цена оставшегося пути и направление.

я не пойму: ты не знаешь как ея влоб решить или тебе нужна оптимизация??

Все парни спасибо. Извините за сумбур. У меня просто мозги работают после того как напишу на форм. Все решил ОК.
Я вот еще подумал про методы сортировки. Но самый элементарный перебором во вложенном цикле, но на это уходит много время. Какие алгоритмы еще существуют? Спасибо...

забей в поисковике, он все найдет

нужно идти из правого нижнего угла, заполняя клеточки длинами наибольших путей, и при заполнении очередной пользоваться уже заполненными.

динамическое программирование:)