3622
правки
Изменения
м
[[Файл:Домино.png|270px|thumb|right|Переходы (1-правильный переход, 2,3-неправильные)]]
→Задача о замощении домино
==='''Решение'''===
[[Файл:Домино.png|270px|thumb|right|Переходы (1-правильный переход, 2,3-неправильные)]]
Для удобства можно хранить профили в виде двоичных масок.
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1</tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>.
Теперь проверим из какого профиля в какой можно перейти.
Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия:
Тогда <tex>a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>
Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i</tex> {{---}} профиль, который может быть последним (т.е. все группы из <tex>0</tex> имеют четные размеры).
==='''Реализация'''===
