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

В заданиях фигурирует работа с файлами: чтение входных данных из них и иногда запись ответа туда. Ссылки на то, как можно работать с файлами:

7.1 Рогалик

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

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

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

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

Сделайте файл roguelike-input.csv, в котором будут содержаться входные данные.

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

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

Результат работы программы также выведите в отдельный файл roguelike-output.txt.

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

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

Пример

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


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

Ввод

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

Вывод

6
RRDRDD

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

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

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

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

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

Сделайте файл lis-input.txt, в котором будут содержаться входные данные.

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

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

Результат работы программы также выведите в отдельный файл lis-output.txt.

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

Примеры

Вход

10
7 1 4 3 3 5 4 8 6 9

Вывод

5
1 3 5 6 9

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

Даны две последовательности чисел: $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

Вход

Сделайте файл lcs-input.txt, в котором будут содержаться входные данные.

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

Выход

Сделайте вывод в консоль.

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

Примеры

Вход

ABCDE
DCDA