Задание 7. Динамическое программирование
7.1 Рогалик
Путешественник хочет пройти из города А в город Б. Так вышло, что между городами огромная прямоугольная пустыня. На своем пути путешественник может найти сундуки с монетами или разбойников, которые могут отобрать скольк-то монет.
Цель путешественника — добраться из А в Б оставив себе как можно больше монет.
Путешетсвенник может ходить только на одну клетку вправо или вниз за один раз.
Входные данные
В первой строке вводится два числа — ширина поля N
и высота поля M
, разделенные пробелом.
Далее идет N
строк, в каждой из которых записано M
чисел, обозначающих количество монет в клетке . Положительная стоимость — нашли сундук и заработали денег, отрицательная — встретили бандитов и отдали "пошлину".
Выходные данные
В первой строке вывести наибольшее количество монет, которое можно собрать.
Во второй строке вывести путь, которым нужно пройти, где R
- right
(направо), D
- down
(вниз).
Пример
Дано такое поле:
0 | 1 | 1 | 0 |
0 | 0 | 2 | 3 |
4 | -2 | 1 | -1 |
-3 | 8 | -6 | 0 |
Ввод
4 4
0 1 1 0
0 0 2 3
4 -2 1 -1
-3 8 -6 0
Вывод
6
RRDRDD
7.2 Наибольшая возрастающая подпоследовательность (НВП)
Дана последовательность чисел . Необходимо найти возрастающую подпоследовательность максимальной длины: , где .
Дана последовательность чисел, найти самую длинную подпоследовательность возрастающих чисел.
Входные данные
В первой строке число n
— количество элементов в последовательности.
На следующей строке n
чисел разделенных пробелом.
Выходные данные
В первой строке число k
— это длина маибольшей подпослдеовательности.
Во второй строке — k
чисел этой подпоследовательности, разделенные пробелом.
Примеры
Вход
10
7 1 4 3 3 5 4 8 6 9
Выход
5
1 3 5 6 9
7.3 Наибольшая общая подпоследовательность (НОП)
Даны две последовательности чисел: и . Требуется найти наибольшую (самую длинную) общую между и подпоследовательность. То есть нужна подпоследовательнось для и одновременно.
Например, , . Тогда наибольшая общая подпоследовательность .
Вход
На первой строке — символы для первой последовательности. На второй строке — символы для второй последовательности.
Выход
Число — длина наибольшей подпоследовательности.
Примеры
Вход
ABCDE
DCDA
Выход
2