ДП по профилю: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 13: | Строка 13: | ||
===Широкий профиль=== | ===Широкий профиль=== | ||
− | Пусть dp[i][j][ | + | Пусть $dp[i][j][mask_{1}][mask_{2}]$ - количество способов замостить доску до $i$-го столбика, притом чтобы $i$-й столбик кодировался маской $mask_{1}$, а $i + 1$-й - $mask_{2}$, и мы сейчас рассматривали $j$-ую позицию в $i$-м столбике |
− | 1) База динамики - dp[0][0][0][0] = 1 | + | 1) База динамики - $dp[0][0][0][0]$ = 1 |
− | 2) Ответ - dp[n - 1][j][(1 << m) - 1][0] | + | 2) Ответ - $dp[n - 1][j][(1 << m) - 1][0]$ |
3) Переходы : | 3) Переходы : | ||
− | Будем перебирать позицию в маске | + | Будем перебирать позицию в маске $mask_{1}$ |
<syntaxhighlight lang="C++" line='line'> | <syntaxhighlight lang="C++" line='line'> | ||
Строка 39: | Строка 39: | ||
===Обычный профиль=== | ===Обычный профиль=== | ||
− | Пусть can[ | + | Пусть $can[mask_{1}][mask_{2}]$ - можно ли в $mask_{1}$ поставить доминошки так, чтобы получить в следующем столбике $mask_{2}$ |
− | Тогда теперь у нас будет dp[i][mask] - мы рассматриваем $i$-ый столбик и хотим в нем собрать mask, сколько способов существует | + | Тогда теперь у нас будет $dp[i][mask]$ - мы рассматриваем $i$-ый столбик и хотим в нем собрать mask, сколько способов существует |
теперь у нас будут очень простые переходы : | теперь у нас будут очень простые переходы : | ||
Строка 60: | Строка 60: | ||
https://wampi.ru/image/6p95C8Q | 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) Переходы - Практически все остается как в широком профиле, единственное нам теперь нужно сдвигать маску вниз, но для этого в плюсах есть операция >> | ||
+ | |||
+ | ===Оценка асимпотики=== | ||
+ | |||
+ | $n \cdot m \cdot 2^m$ | ||
+ | |||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 19:41, 16 декабря 2019
Содержание
Задача
Нам дана обычная фигурка для домино($1 \times 2$), мы можем ее класть на поле в виде $1 \times 2$ или $2 \times 1$. Требуется сказать количество способов замостить доску доминошками
Наивное решение
Давайте запустим перебор рекурсией и честно посчитаем количество способов. Это работает за очень долго. Подумаем, как это оптимизировать.
Динамика
Заметим, что столбик однозначно определяется двоичной маской(0 - свободно, 1 - покрывается какой-то доминошкой), но мы уже научились делать динамику по подмаскам, давайте применим здесь ту же идею.
Широкий профиль
Пусть $dp[i][j][mask_{1}][mask_{2}]$ - количество способов замостить доску до $i$-го столбика, притом чтобы $i$-й столбик кодировался маской $mask_{1}$, а $i + 1$-й - $mask_{2}$, и мы сейчас рассматривали $j$-ую позицию в $i$-м столбике
1) База динамики - $dp[0][0][0][0]$ = 1
2) Ответ - $dp[n - 1][j][(1 << m) - 1][0]$
3) Переходы :
Будем перебирать позицию в маске $mask_{1}$
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[mask_{1}][mask_{2}]$ - можно ли в $mask_{1}$ поставить доминошки так, чтобы получить в следующем столбике $mask_{2}$
Тогда теперь у нас будет $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
Тогда теперь у нас есть $dp[i][j][mask]$ - сколько способов дойти до $j$ ячейки $i$ строки с маской $mask$ у нас есть
1) База $dp[0][0][0] = 1$
2) Ответ - в зависимости от реализации, но я обычно пишу так, чтобы ответ лежал в $dp[n][0][0]$ - нулевая строка столбика, которого нет в таблице и маска равна 0
3) Переходы - Практически все остается как в широком профиле, единственное нам теперь нужно сдвигать маску вниз, но для этого в плюсах есть операция >>
Оценка асимпотики
$n \cdot m \cdot 2^m$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin