Помогите с ДП по изломанному профилю

Правка ru4, от VladKov, 2019-11-20 04:33:38

Не могу разобраться с Динамикой по профилю. В интернете материала мало, понимаю по теории с 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 нашел такой код, и что то мне подсказывает, что это и есть дп по излому. (/predownloaded/51/d8/51d86550f605444e4d78a0472a50d9b25976d1b7.jpg)

Код взят к задачи о доминошках. Не могу понять, почему профилей (1 << n), а не (2 << n), что тогда j,и почему при подсчёте маски следующего столбца мы добавляем результат в этот же столбец? Всем благодарен

Теги дп, профиль

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru8 Русский VladKov 2019-11-20 07:34:44 32
en4 Английский VladKov 2019-11-20 06:16:46 6 Tiny change: ' times in n. But t' -> ' times in range n. But t'
en3 Английский VladKov 2019-11-20 06:10:49 0 (published)
en2 Английский VladKov 2019-11-20 06:10:29 3 Tiny change: 'Works fast\n And I c' -> 'Works fast.\n\n And I c' (saved to drafts)
en1 Английский VladKov 2019-11-20 06:09:41 1028 Initial revision for English translation
ru7 Русский VladKov 2019-11-20 06:02:36 41
ru6 Русский VladKov 2019-11-20 04:35:57 89
ru5 Русский VladKov 2019-11-20 04:34:12 60
ru4 Русский VladKov 2019-11-20 04:33:38 71
ru3 Русский VladKov 2019-11-20 04:32:55 2 Мелкая правка: 'явления мечта излома ' -> 'явления места излома '
ru2 Русский VladKov 2019-11-20 04:31:50 53
ru1 Русский VladKov 2019-11-20 04:30:27 960 Первая редакция (опубликовано)