DP по подмаскам

DP по подмаскам

Submask DP — это битмасковая техника, где для фиксированной маски мы эффективно перебираем все её подмаски.

Основной приём: перебор всех подмасок маски

Для маски m этот цикл проходит по всем ненулевым подмаскам m:

Если вам также нужна подмаска 0, обработайте её отдельно.

Почему это работает?

• s - 1 изменяет младший установленный бит и все биты после него
• & m убирает биты, которых нет в исходной маске
• поэтому мы остаёмся внутри подмасок m

Факт о сложности (очень важно)

Если вы запускаете цикл по подмаскам для каждой маски, общая сложность:

$O(3^n)$

Причина: для каждого бита есть 3 варианта:

• не в маске
• в маске, но не в подмаске
• и в маске, и в подмаске

Пример: разбиение множества на допустимые группы

Предположим:

• ok[s] говорит, является ли подмножество s допустимой группой
• Мы хотим минимальное число групп, чтобы покрыть маску m

Пусть:

$dp[m] = \text{минимум групп, чтобы покрыть } m$