arts
09.12.2010 10:03 nedobook
Есть прямоугольное поле, на ячейках которого лежат монеты (количество
задано целым числом). Есть фишка, которая двигается из левого нижнего угла в
правый верхний, за один ход перемещаясь либо вправо, либо вверх. Необходимо
собрать максимальную сумму монет на пройденных ячейках.
23 comments
recommend
bookmark
subscribe
Простенькая задачка на очередь.
динамическое программирование
Вроде несложно.
Ну так предлагай решения, ёпт.
Зачем?
Мне интересно, как другие эту задачу решат.
у нее одно правильное решение: методами динамического программирования. ссылки кидать не буду, все есть в гугле
man динамическое программирование
Простейший (разумеется неправильный) способ: смотрим, где больше осталось потенциально доступных для собирания монеток — в строке или в столбце) — и идем, соответственно, вправо или влево.
Влево нельзя.
Я в курсе.
не влево а вверх.
#ofgtf/11
#ofgtf/12
программеры-программерчики
Если по краям поля поставить по 100, а внутри по 1, то алгоритм будет работать неправильно.
Я и написал, что он неправильный :-)
видит Б-г, не хотел уходит из RL в п100 в этом году, но не вытерпел:
создаём копию поля, такого же размера, проходим последовательно ячейки по диагоналям идущим слева сверху вправо вниз начиная из правого верхнего угла. т.е. примерно такой порядок обхода 3×4:
__7__4__2__1
10__8__5__3
12_11__9__6
для всех клеток в порядке обхода прибавляем значение лежащее в соответствующей ячейке исходного поля к максимуму из значений лежащих в смежных клетках справа и сверху, если одной или обоих таких клеток нет (т.е. мы на границе поля), то считается что в них лежит нуль. (заодно запоминаем значение какой из клеток прибавили (чтоб проще было обратный путь строить)).
тащем-та когда алгоритм дойдёт до левого нижнего поля, то в нём окажется набранной максимальная возможная сумма. ну а обратный путь построить уже очевидно как.
З.Ы. @arts, спасибо за альтернативу жуйку.
ты съебался оттуда?
в тот же день когда пошла первая волна предупреждений
Вернусь из универа — разберусь с твоим решением. А также, если мне будет не лень, напишу расово верное.
динамическое программирование
;)
тред не читай @ сразу отвечай
тред читал, дублированным ответом лишний раз подъебал.
;)
Клёвый алгоритм получился. Моё решение с очередью проще кодом написать, чем объяснять, поэтому не буду этим заморачиваться.