Динамика по маскам

Когда состояние — это подмножество небольшого набора, его кодируют числом: бит $i$ равен единице, если элемент $i$ в подмножестве.

Такое состояние занимает $2^n$ значений. При $n \le 20$ это миллион — приемлемо; при $n = 25$ уже 33 миллиона и обычно поздно.

Пример: гамильтонов путь

Найти путь минимального веса, проходящий через все вершины по разу.

Чего не хватает, если хранить только маску посещённых? Того, где мы сейчас стоим: продолжить путь можно только из последней вершины.

$dp[\text{mask}][v]$ — минимальный вес пути, посетившего ровно вершины из маски и закончившегося в $v$.

vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
for (int v = 0; v < n; v++) dp[1 << v][v] = 0;

for (int mask = 1; mask < (1 << n); mask++)
    for (int v = 0; v < n; v++) {
        if (dp[mask][v] >= INF || !(mask >> v & 1)) continue;
        for (int u = 0; u < n; u++) {
            if (mask >> u & 1) continue;             // u уже посещена
            if (w[v][u] >= INF) continue;            // ребра нет
            long long& cell = dp[mask | (1 << u)][u];
            cell = min(cell, dp[mask][v] + w[v][u]);
        }
    }

Состояний $2^n \cdot n$, переходов из каждого $n$ — итого $O(2^n n^2)$.

Проверено: на 4 000 графов до семи вершин совпало с перебором всех перестановок.

Измерено, сколько это стоит:

$n$	$2^n n^2$	время
16	$1{,}7\cdot10^7$	29 мс
18	$8{,}5\cdot10^7$	135 мс
20	$4{,}2\cdot10^8$	620 мс

Граница проходит примерно по $n = 20$: дальше не помещается ни во время, ни в память.

Почему порядок обхода масок работает

Маски перебираются по возрастанию числа. Переход mask -> mask | (1 << u) всегда увеличивает число: мы устанавливаем бит, который был нулём.

Значит, к моменту обработки маски все маски, из которых в неё можно попасть, уже обработаны. Топологический порядок получается сам, без всякого топсорта, — и это общая причина, почему динамика по маскам пишется простым for.

Пример: когда позиция не нужна

Есть $n$ встреч. На встречу $i$ можно прийти, только если текущее настроение лежит в $[a_i, b_i]$; после встречи настроение меняется на $+c_i$. Начальное настроение $k$. Максимум встреч.

Здесь номер последней встречи в состояние не нужен. Настроение после набора встреч равно $k + \sum_{i \in \text{mask}} c_i$ и от порядка не зависит.

Поэтому $dp[\text{mask}]$ — просто «достижима ли такая маска», а ответ — маска с наибольшим числом единиц. Состояний $2^n$ вместо $2^n n$.

Вывод общий: прежде чем добавлять параметр в состояние, проверьте, влияет ли он на будущее. Здесь не влиял.

Функция от маски за суммарную линию

Считать $\sum_{i \in \text{mask}} c_i$ перебором битов — это $O(2^n n)$ на всё. Можно за $O(2^n)$.

Возьмём любой установленный бит маски и сведём к маске без него:

vector<long long> sum(1 << n, 0);
for (int mask = 1; mask < (1 << n); mask++) {
    int b = __builtin_ctz(mask);            // младший установленный бит
    sum[mask] = c[b] + sum[mask ^ (1 << b)];
}

__builtin_ctz — число нулей в конце двоичной записи, то есть номер младшего единичного бита. Одна процессорная инструкция.

Проверено: на 20 000 наборов совпало с прямым подсчётом.

В приведённой задаче эта оптимизация не нужна — там доминирует другой цикл. Но встречаются задачи, где подсчёт функции по маскам и есть основная работа.

Типовые применения

задача	состояние
гамильтонов путь, задача коммивояжёра	маска + последняя вершина
разбиение множества на группы	маска обработанных
паросочетание в двудольном графе с малой долей	маска занятых справа + номер слева
раскраска графа в $k$ цветов	маска покрашенных
покрытие множества подмножествами	маска покрытых

Во всех случаях ограничение читается прямо из условия: если в задаче написано $n \le 20$ и речь про подмножества — это маски.