Изменения
Нет описания правки
== Динамика по изломанному профилю ==
{{Определение|definition='''Изломанный профиль''' (англ. ''broken profile'') {{- --}} обобщение прямого профиля на случай, когда обработанным является не целое число столбцов, а некоторое количество столбцов и несколько первых клеток следующего столбца. }}
Это очень сильная оптимизация динамики по профилю. Идея в том, чтобы добиться как можно меньшего числа переходов (от одного профиля к другому). Теперь профиль — это не только маска, но ещё и место излома. Выглядит это так:
== Пример ==
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через i-ю горизонталь сверху вниз, она переходит на предыдущую вертикаль и спускается до низу.
Профилем будет пара <tex>(p, i)</tex>, в <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i + 1</tex>. Горизонтали будем нумеровать с нуля, так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>n - 1</tex>.
Для двух профилей pr1 = (p1, i1)и pr2 = (p2, i2) положим d[pr1][pr2] = 1 если и только если:
а)если i < n - 1, то i1 + 1 = i2; иначе i2 = 0;
б)можно так положить доминошку, накрывающую (i + 1)-й квадратик, что после этого в p2 будет храниться в точности информация о соответствующих квадратиках.
Проще говоря, доминошку можно класть только двумя способами -- как показано на рисунках (на (i + 1)-й квадратик можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если (i + 1)-я клетка занята, то доминошку уже не надо класть, и (p, i) логично отождествить с (p, i + 1) ("i + 1" пишется условно, нужно всегда иметь в виду возможность i = n - 1).
Легко заметить, что количество профилей увеличилось в 2n раз (добавилось число от 1 до n и еще один бит). Но зато количество переходов резко сократилось с 2n до 2.
== См. также ==
