Не могу разобраться с Динамикой по профилю. В интернете материала мало, понимаю по теории с informatics(https://informatics.msk.ru/mod/resource/view.php?id=5113) и neerc.ifmo. Задача паркет о замощении доминошками 2*1, 1*2 поля n*m. На e-maxx нашел следующий код. (http://e-maxx.ru/algo/profile_dynamics) По моим расчетам, асимптотика составляет O(n*m*2^(2n)), так как calc в худшем случае будет вызаваться по 2 раза по всей длине n. Так ли это? В комментариях указано O(n*m*2^n). Работает быстро И не могу понять дп по излом. профилю. Я читал теорию, о увеличении профилей в 2n, за счёт появления места излома — от 1 до n, и дополнительного бита в маске. Тем не менее, нигде код не нашел. На codeforces нашел такой код, и что то мне подсказывает, что это и есть дп по излому. (https://codeforces.net/gym/100124/submission/2804558)
Код взят к задачи о доминошках. Не могу понять, почему профилей (1 << n), а не (2 << n), что тогда j,и почему при подсчёте маски следующего столбца мы добавляем результат в этот же столбец? Всем благодарен
Автокомментарий: текст был обновлен пользователем VladKov (предыдущая версия, новая версия, сравнить).
То что на e-maxx — не динамика по изломанному профилю. Раздел
3из pdf-ки прилинкованной это довольно близко к тому что на e-maxx. Можно оценить как $$$O(n \cdot 2^{2 \cdot m})$$$. Однако на самом деле будет быстрее, так как не все профили между собой совместимы (т.е. не из каждого $$$2^m$$$ состояний можно перейти в другие $$$2^m$$$).По сути у нас $$$O(n \cdot 2^m)$$$ состояний и из каждого $$$O(2^m)$$$ переходов.
Решение https://codeforces.net/gym/100124/submission/2804558, которые в посте упомянуто — динамика по изломанному профилю.
В упомянутой pdf-ке это раздел
8. Кажется, там достаточно нормально описано и визуализировано как это работает. Просто может стоит посидеть с листком и порисовать :)В динамике по изломанному профилю у нас заполнены первые
iстолбцов доминошками, которые полностью лежат в первыхiстолбцах (т.е. возможны какие-то пропуски, если доминошка будет лежать вiиi+1столбцах). И столбецi+1заполнен только частично. А именно мы заполнили первыеjстрок этого столбца.Соответственно состояние:
i— номер последнего столбца который мы полностью заполнили (за вычетом доминошек, которые на половину будут лежать вi+1).j— столбец до которого (исключительно) мы заполнили столбецi+1.Профиль столбца
i.Профиль столбца
i+1.Но так как мы столбец
i+1заполнили только частично, соответсвенно нам нужно знать только первыеjстрок этого профиля. С другой стороны, этиjстрокi+1-го столбца "перекрывают" столбецi. Т.е. когда мы будем заполнять другие клетки столбцаi+1или клетки[0..j)столбцаi+2, то клетки[0..j)столбцаiникак на это влиять уже не будут, поэтому нам не нужно их знать.В итоге, нам нужно только знать клетки
[0..j)столбцаi+1и клетки[j..n)столбцаi. Поэтому, собственно, профиль и называется изломанным.Получается, что состояний $$$O(m \cdot n \cdot 2^n)$$$ и количество переходов $$$O(1)$$$ -- перебрать как поставить доминошку в текущую клетку
(i, j)(место излома профиля).Ну и в итоге, получаем $$$O(m \cdot n \cdot 2^n)$$$.