Динамическое программирование по профилю, Василевский Б.
К большинству олимпиадных задач ограничения (по времени, по памяти) жюри подбирает по принципу «как можно больше». То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное — нет.
Когда встречается задача с маленькими ограничениями (например, до 10), это означает, что либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором.
Динамическое программирование по профилю — одна из таких оптимизаций. Часто в таких задачах дело происходит на прямоугольной таблице, одна из размерностей которой достаточно мала (не более 10). Требуется проверить существование, посчитать количество способов, стоимость и т. д. (как в обычном динамическом программировании). Асимптотика алгоритма, основанного на этой идее, является экспоненциальной только по одной размерности, а по второй — линейная или даже лучше.
Задача о замощении домино.
Чтобы понять, что такое динамика по профилю, будем рассматривать разные задачи и разбирать их решения с помощью этого приема.
Для начала рассмотрим известную задачу: дана таблица n х m, нужно найти количество способов полностью замостить ее неперекрывающимися костяшками домино (прямоугольниками 2 х 1 и 1 х 2). Считаем n, m < 10.
Заметим, что в процессе замощения каждая клетка таблицы будет иметь одно из двух состояний: покрыта какой-нибудь доминошкой или нет. Чтобы запомнить состояние клеток одного столбца, достаточно одной переменной Р типа integer. Положим i-й бит Р равным 1, если i-я сверху клетка данного столбца занята, 0 — если свободна. Будем говорить в таком случае, что Р — битовая карта нашего столбца.
Теперь дадим определение базовой линии и профиля.
Базовой линией будем называть вертикальную прямую, проходящую через узлы таблицы.
Можно занумеровать все базовые линии, по порядку слева направо, начиная с нуля. Таким образом, базовая линия с номером i — это прямая, отсекающая первые i столбцов от всех остальных (если такие имеются).
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Динамическое программирование по профилю, Василевский Б. - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по программированию :: программирование :: Василевский
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Учимся кодить на JavaScript, Мориц Д., 2019
- Длинная арифметика, Неспирный В.Н., 2010
- Классические задачи Computer Science на языке Python, Копец Д., 2020
- Быстрое преобразование Фурье и многочлены, Кульков А., 2017
Предыдущие статьи:
- Прикладное программирование с использованием языка С-Шарп, Бельков С.А., 2017
- Практика программирования в инженерных расчётах, Николаев В.Т., Купцов С.В., Тикменов В.Н., 2018
- Методы рекурсивного программирования, Забродина С.П., Иваненко В.Г., Кулябичева Ю.П., Иващенко Н.И., Бердж В., 1983
- Линейное программирование в современных задачах оптимизации, Бородакий Ю.В., Загребаев A.M., Крицына Н.А., Кулябичев Ю.П., Шумилов Ю.Ю., 2008