Задача про Буратино

Буратино бежит по полю в Стране дураков и срывает с выросших из его монеток деревьев деньги. За ним гонится Карабас-Барабас, так что времени обходить все деревья нет, можно только пробежать один раз из правого верхнего угла в левый нижний. При этом один раз за всё поле Буратино может воззвать к доброй лисе Алисе, которая добавит ему в карман число монет, равное удвоенной последней цифре текущей суммы у него в кармане. Проложите подходящий маршрут, и укажите, в какой момент лучше обращаться к Алисе.

Формат входных данных
Программа получает на вход через пробел r, c - количество строк и столбцов в матрице (количество рядом деревьев и деревьев в ряду). Потом r строк, каждая из которых состоит из c чисел, разделённых пробелами. Каждое число соответствует количеству монет, которые можно собрать с данного дерева. Все числа целые, в пределах от 1 до 100 включительно.

Формат выходных данных
Программа выводит на экран наибольшее количество монет, которое может собрать Буратино, если он будет идти от верхнего правого угла поля до нижнего левого угла включительно. Он может перемещаться только вниз и влево. При этом, когда он попадает на клетку с числом Х, количество монет у него увеличивается на Х. Также один раз после перехода в какую-то клетку дополнительно Буратино добавится 2Х монет, где Х - младшая цифра в количестве монет в его кармане на момент прихода в данную клетку.

После количества монет программа выводит маршрут Буратино, состоящий из букв Н (вниз), Л (влево), А (Алиса), суммарно букв должно быть r + c - 1. Буква А встречается в маршруте ровно один раз, при одинаковых итоговых суммах - как можно раньше. Буквы разделены пробелами.

Пример
Ввод
3 6
6 3 7 8 5 7
6 9 1 7 9 9
1 1 4 3 2 5

Вывод
67
Н Л Л Л Л Л Н А

0

Стандартное применение динамического программирования.
Заполняете еще одно поле такого же размера. В клетке [i][j] будут храниться два числа: сумма сбора по клеткам и подарок от Алисы. Заполняется справа налево и сверху вниз. При заполнении клетки [i][j] мы должны анализировать клетку сверху и клетку справа и понять, с какого направления выгоднее попадать в клетку [i][j]. Алгоритм выбора, по-моему, очевиден. В итоге нижняя левая клетка будет содержать ответ. Потом восстанавливаем путь обратным просмотром и проходом пути вперед ищем место, где нужно поставить A.

Добавлено через 2 минуты
Для простоты восстановления пути можно в клетке [i][j] при заполнении таблицы сохранять еще направление, откуда мы в эту клетку пришли - сверху или справа.

1