Не могу разобраться с Динамикой по профилю. В интернете материала мало, понимаю по теории с informatics(https://informatics.msk.ru/mod/resource/view.php?id=5113) и neerc.ifmo. Понимаю на примере задачи паркет о замощении доминошками 2*1, 1*2. На e-maxx нашел следующий код. (http://e-maxx.ru/algo/profile_dynamics)↵
По моим расчетам, асимптотика составляет O(n*m*2^(2n)), так как calc в худшем случае будет выдаваться по 2 раза. Так ли это? В комментариях указано O(n*m*2^n).↵
И не могу понять дп по профилю. Я читал теорию, о увеличении профилей в 2n, за счёт появления мечста излома — от 1 до n, и дополнительного бита в маске. Тем не менее, нигде код не нашел. На codeforces нашел такой код, и что то мне подсказывает, что это и есть дп по излому. (см. ниже)↵
↵
Код взят к задачи о доминошках. Не могу понять, почему профилей (1 << n), а не (2 << n), что тогда j,и почему при подсчёте маски следующего столбца мы добавляем результат в этот же столбец?↵
Всем благодарен
По моим расчетам, асимптотика составляет O(n*m*2^(2n)), так как calc в худшем случае будет выдаваться по 2 раза. Так ли это? В комментариях указано O(n*m*2^n).↵
И не могу понять дп по профилю. Я читал теорию, о увеличении профилей в 2n, за счёт появления ме
↵
Код взят к задачи о доминошках. Не могу понять, почему профилей (1 << n), а не (2 << n), что тогда j,и почему при подсчёте маски следующего столбца мы добавляем результат в этот же столбец?↵
Всем благодарен
