#2965

Темы: [Динамическое программирование на таблицах]

В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы.

Формат входных данных

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат выходных данных

Программа должна вывести единственное число: максимальную возможную стоимость маршрута черепашки.

Ввод Вывод

3 4
1 1 2 1
2 2 1 1
2 1 2 1

9

Ввод	Вывод
3 4 1 1 2 1 2 2 1 1 2 1 2 1	9

#2966

Вывести маршрут максимальной стоимости

Темы: [Динамическое программирование на таблицах]

В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

Входные данные

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Выходные данные

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

Входные данные

Выходные данные

74
D D R R R R D D

#2991

Последовательности из 0 и 1 без двух единиц подряд

Темы: [Динамическое программирование: последовательности]

По данному натуральному n определите количество последовательностей длины n из 0 и 1, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 2³¹-1.

Входные данные

Вводится натуральное число.

Выходные данные

Выведите ответ на задачу.

Примеры

Входные данные

Выходные данные

#2992

Последовательности из 0, 1, 2 без двух единиц подряд

Темы: [Динамическое программирование: последовательности]

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 2³¹-1.

Входные данные

Вводится натуральное число.

Выходные данные

Выведите ответ на задачу.

Примеры

Входные данные

Выходные данные

#2993

Последовательности из 0, 1 и 2 без двух единиц и двоек подряд

Темы: [Динамическое программирование: последовательности]

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд и двух двоек подряд. Гарантируется, что ответ не превосходит 2³¹-1.

Входные данные

Вводится натуральное число.

Выходные данные

Выведите ответ на задачу.

Примеры

Входные данные

Выходные данные