ДП по профилю: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «===Задача=== Нам дана обычная фигурка для домино($1 \times 2$), мы можем ее класть на поле в виде $...»)
 
Строка 55: Строка 55:
 
К сожалению оба способа работают достаточно долго, а именно Широкий профиль за $O(n \cdot m \cdot 2^m \cdot 2^m)$, так как мы перебираем столбик, строку, первую и вторую маску, Обычный же за $O(n \cdot 2^m \cdot 2^m)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль
 
К сожалению оба способа работают достаточно долго, а именно Широкий профиль за $O(n \cdot m \cdot 2^m \cdot 2^m)$, так как мы перебираем столбик, строку, первую и вторую маску, Обычный же за $O(n \cdot 2^m \cdot 2^m)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль
  
====Изломанный профиль====
+
===Изломанный профиль===
  
 +
Уже в названии подхода содержится его идея - давайте сломаем нашу маску, пускай теперь маска означает не весь $i$-й столбик, а ячейки с $j$-ячейки $i$-ого столбика до $m - 1$-й ячейки $i$-ого столбика и ячейки с $0$-ячейки $i + 1$-ого столбика до $j + 1$-й ячейки $i + 1$-ого столбика
 +
 +
https://wampi.ru/image/6p95C8Q
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}

Версия 22:36, 16 декабря 2019

Задача

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

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

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

Динамика

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

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

Пусть dp[i][j][mask1][mask2] - количество способов замостить доску до $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

1 for (int j = 0; j < m; j++) {
2     if ((1 << j) & mask1) { //j-й бит уже занят и поэтому мы не можем поставить доминошки
3         continue;
4     }
5     dp[i][j + 1][mask1 | (1 << j)][mask2 | (1 << j)] += dp[i][j][mask1][mask2]; //горизонтальная, рассмотреть случай, если мы на границе столбика
6     if ((1 << (j + 1)) & mask1) { //(j + 1)-й бит свободен, надо проверить еще, что он существует
7         dp[i][j + 2][mask1 | (1 << j) | (1 << (j + 1))][mask2] += dp[i][j][mask1][mask2];//также рассмотреть границу отдельно
8     }
9 }

В данной идее много граничных случаев, поэтому сейчас мы рассмотрим два других решения этой задачи

Обычный профиль

Пусть can[mask1][mask2] - можно ли в mask1 поставить доминошки так, чтобы получить в следующем столбике mask2

Тогда теперь у нас будет dp[i][mask] - мы рассматриваем $i$-ый столбик и хотим в нем собрать mask, сколько способов существует

теперь у нас будут очень простые переходы :

1 for (int mask1 = 0; mask1 < (1 << m); mask1++) {
2      dp[i + 1][mask1] += dp[i][mask] * can[mask][mask1];
3 }

Оценка асимпотики

К сожалению оба способа работают достаточно долго, а именно Широкий профиль за $O(n \cdot m \cdot 2^m \cdot 2^m)$, так как мы перебираем столбик, строку, первую и вторую маску, Обычный же за $O(n \cdot 2^m \cdot 2^m)$, что лучше но все равно долго, поэтому иногда используют другой способ - изломанный профиль

Изломанный профиль

Уже в названии подхода содержится его идея - давайте сломаем нашу маску, пускай теперь маска означает не весь $i$-й столбик, а ячейки с $j$-ячейки $i$-ого столбика до $m - 1$-й ячейки $i$-ого столбика и ячейки с $0$-ячейки $i + 1$-ого столбика до $j + 1$-й ячейки $i + 1$-ого столбика

https://wampi.ru/image/6p95C8Q


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

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