ДП по профилю

Задача

Нам дана обычная фигурка для домино($1 \times 2$), мы можем ее класть на поле в виде $1 \times 2$ или $2 \times 1$. Требуется сказать количество способов замостить доску доминошками

Наивное решение

Давайте запустим перебор рекурсией и честно посчитаем количество способов. Это работает за очень долго. Подумаем, как это оптимизировать.

Динамика

Заметим, что столбик однозначно определяется двоичной маской(0 - свободно, 1 - покрывается какой-то доминошкой), но мы уже научились делать динамику по подмаскам, давайте применим здесь ту же идею.

Широкий профиль

Пусть $dp[i][j][mask_{1}][mask_{2}] - количество способов замостить доску до $i$-го столбика, притом чтобы $i$-й столбик кодировался маской mask1, а $i + 1$-й - $mask2$, и мы сейчас рассматривали $j$-ую позицию в $i$-м столбике 1) База динамики - $dp[0][0][0][0]$ = 1 2) Ответ - $dp[n - 1][j][(1 << m) - 1][0]$ 3) Переходы : Будем перебирать позицию в маске mask1 '"`UNIQ--syntaxhighlight-00000000-QINU`"' В данной идее много граничных случаев, поэтому сейчас мы рассмотрим два других решения этой задачи ==='"`UNIQ--h-4--QINU`"'Обычный профиль=== Пусть $can[mask_{1}][mask_{2}]$ - можно ли в $mask_{1}$ поставить доминошки так, чтобы получить в следующем столбике $mask_{2}$ Тогда теперь у нас будет $dp[i][mask]$ - мы рассматриваем $i$-ый столбик и хотим в нем собрать mask, сколько способов существует теперь у нас будут очень простые переходы : '"`UNIQ--syntaxhighlight-00000002-QINU`"' ==='"`UNIQ--h-5--QINU`"'Оценка асимпотики=== К сожалению оба способа работают достаточно долго, а именно Широкий профиль за $O(n \cdot m \cdot 2^m \cdot 2^m)$, так как мы перебираем столбик, строку, первую и вторую маску, Обычный же за $O(n \cdot 2^m \cdot 2^m)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль ==='"`UNIQ--h-6--QINU`"'Изломанный профиль=== Уже в названии подхода содержится его идея - давайте сломаем нашу маску, пускай теперь маска означает не весь $i$-й столбик, а ячейки с $j$-ячейки $i$-ого столбика до $m - 1$-й ячейки $i$-ого столбика и ячейки с $0$-ячейки $i + 1$-ого столбика до $j + 1$-й ячейки $i + 1$-ого столбика https://wampi.ru/image/6p95C8Q Тогда теперь у нас есть $dp[i][j][mask]$ - сколько способов дойти до $j$ ячейки $i$ строки с маской $mask$ у нас есть 1) База $dp[0][0][0] = 1$ 2) Ответ - в зависимости от реализации, но я обычно пишу так, чтобы ответ лежал в $dp[n][0][0]$ - нулевая строка столбика, которого нет в таблице и маска равна 0 3) Переходы - Практически все остается как в широком профиле, единственное нам теперь нужно сдвигать маску вниз, но для этого в плюсах есть операция >> ==='"`UNIQ--h-7--QINU`"'Оценка асимпотики=== $n \cdot m \cdot 2^m$

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin