Задание 7. Динамическое программирование

7.1 Рогалик

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

Цель путешественника — добраться из А в Б оставив себе как можно больше монет.

Путешетсвенник может ходить только на одну клетку вправо или вниз за один раз.

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

В первой строке вводится два числа — ширина поля N и высота поля M, разделенные пробелом.

Далее идет N строк, в каждой из которых записано M чисел, обозначающих количество монет в клетке $a_{ij}$ . Положительная стоимость — нашли сундук и заработали денег, отрицательная — встретили бандитов и отдали "пошлину".

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

В первой строке вывести наибольшее количество монет, которое можно собрать.

Во второй строке вывести путь, которым нужно пройти, где R - right(направо), D - down(вниз).

Пример

Дано такое поле:


0	1	1	0
0	0	2	3
4	-2	1	-1
-3	8	-6	0

Ввод

Вывод

6
RRDRDD

7.2 Наибольшая возрастающая подпоследовательность (НВП)

Шаблон на repl.it

Дана последовательность чисел $a_1, a_2, ..., a_n$ . Необходимо найти возрастающую подпоследовательность максимальной длины: $a_{i_1} < a_{i_2} < ... < a_{i_k}$ , где $i_1 < i_2 < ... < i_k$ .

Дана последовательность чисел, найти самую длинную подпоследовательность возрастающих чисел.

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

В первой строке число n — количество элементов в последовательности. На следующей строке n чисел разделенных пробелом.

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

В первой строке число k — это длина маибольшей подпослдеовательности. Во второй строке — k чисел этой подпоследовательности, разделенные пробелом.

Примеры

Вход

10
7 1 4 3 3 5 4 8 6 9

Выход

5
1 3 5 6 9

7.3 Наибольшая общая подпоследовательность (НОП)

Шаблон на repl.it

Даны две последовательности чисел: $X = [x_1, x_2, ..., x_n]$ и $Y = [y_1, y_2, ..., y_m]$ . Требуется найти наибольшую (самую длинную) общую между $X$ и $Y$ подпоследовательность. То есть нужна подпоследовательнось $Z$ для $X$ и $Y$ одновременно.

Например, $X = [A, B, C, D, E]$ , $Y = [D, C, D, A]$ . Тогда наибольшая общая подпоследовательность $Z = [C, D]$ .

Теория по НОП на itmo wiki

Вход

На первой строке — символы для первой последовательности. На второй строке — символы для второй последовательности.

Выход

Число — длина наибольшей подпоследовательности.

Примеры

Вход

ABCDE
DCDA

Выход