Динамическое программирование для основных групп

Условия задач на динамическое программирование для основных групп

Черепаха

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=656&chapterid=2965

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

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

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

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

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

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

Маршрут черепашки

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=656&chapterid=2966

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

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

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

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

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

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

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

Формат входных данных Одно число 1 ≤ N ≤ 20.

Формат выходных данных Одно число — количество безопасных вариантов формирования стопки.

Пример:

Взрывоопасность-2

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

Формат входных данных Одно число 1 ≤ N ≤ 20.

Формат выходных данных Одно число — количество безопасных вариантов формирования стопки.

Пример:

Без трех единиц

Определите количество последовательностей из нулей и единиц длины N (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.

Формат входных данных Одно число 1 ≤ N ≤ 40.

Формат выходных данных Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹ − 1.

Пример:

Подсказка: Рассмотрим последовательности длины N, на первом месте может стоять 0, таких будет f(N-1), при подстановке 1, второе может быть 0, таких будет f(N-2), и 1,таких f(N-3). Так как трех единиц не может быть, по условию, просто просуммируем полученные значения до нужного N, записывая каждый в массив: f[n] = f[n-1] + f[n-2] + f[n-3]; Ответ будет находиться в f[n];

Калькулятор

Имеется калькулятор, который выполняет три операции:

1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Формат входных данных Одно число 1 ≤ N ≤ 10⁶.

Формат выходных данных Одно число: наименьшее количество искомых операций.

Пример:

Подсказка: Предположим в массиве a[i] при i<N лежит для каждого i минимальное количество операций, которым можно это i получить из 1. Вычислим a[N].

Калькулятор с восстановлением ответа

Имеется калькулятор, который выполняет три операции:

1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Формат входных данных Одно число 1 ≤ N ≤ 10⁶.

Формат выходных данных Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.

Пример:

Подсказка: Предположим в массиве a[i] при i<N лежит для каждого i минимальное количество операций, которым можно это i получить из 1. Вычислим a[N].

Теперь пойдем обратным ходом от a[N] к a[1], занося в массив b[] какую операцию применять (1, 2 или 3). Напечатаем запомненные в b числа в обратном порядке.

Последовательность из 0 и 1 длины N

Выведите все последовательности из 0 и 1 длины N.

Формат входных данных Одно число 1 ≤ N ≤ 10.

Формат выходных данных Последовательности из 0 и 1, по одной последовательности на строку, от наименьшей к наибольшей.

Пример:

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

Выведите все последовательности из 0 и 1 длины N, в которых нет двух подряд идущих единиц.

Формат входных данных Одно число 1 ≤ N ≤ 10.

Формат выходных данных Последовательности из 0 и 1, по одной последовательности на строку, от наименьшей к наибольшей.

Пример:

LCS Longest Common Subsequence (наибольшая общая подпоследовательность)