Динамическое программирование по профилю, Василевский Б.

Динамическое программирование по профилю, Василевский Б.

   К большинству олимпиадных задач ограничения (по времени, по памяти) жюри подбирает по принципу «как можно больше». То есть чтобы любые разумные реализации правильного решения проходили, а всё остальное — нет.
Когда встречается задача с маленькими ограничениями (например, до 10), это означает, что либо автор намеренно сбивает Вас с правильного пути, либо действительно эта задача решается каким-то (оптимизированным) перебором.
Динамическое программирование по профилю — одна из таких оптимизаций. Часто в таких задачах дело происходит на прямоугольной таблице, одна из размерностей которой достаточно мала (не более 10). Требуется проверить существование, посчитать количество способов, стоимость и т. д. (как в обычном динамическом программировании). Асимптотика алгоритма, основанного на этой идее, является экспоненциальной только по одной размерности, а по второй — линейная или даже лучше.




Задача о замощении домино.
Чтобы понять, что такое динамика по профилю, будем рассматривать разные задачи и разбирать их решения с помощью этого приема.

Для начала рассмотрим известную задачу: дана таблица n х m, нужно найти количество способов полностью замостить ее неперекрывающимися костяшками домино (прямоугольниками 2 х 1 и 1 х 2). Считаем n, m < 10.

Заметим, что в процессе замощения каждая клетка таблицы будет иметь одно из двух состояний: покрыта какой-нибудь доминошкой или нет. Чтобы запомнить состояние клеток одного столбца, достаточно одной переменной Р типа integer. Положим i-й бит Р равным 1, если i-я сверху клетка данного столбца занята, 0 — если свободна. Будем говорить в таком случае, что Р — битовая карта нашего столбца.

Теперь дадим определение базовой линии и профиля.
Базовой линией будем называть вертикальную прямую, проходящую через узлы таблицы.
Можно занумеровать все базовые линии, по порядку слева направо, начиная с нуля. Таким образом, базовая линия с номером i — это прямая, отсекающая первые i столбцов от всех остальных (если такие имеются).



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Динамическое программирование по профилю, Василевский Б. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Василевский