A Programação Dinâmica com Máscaras de Bits (Bitmask DP) é uma técnica poderosa para resolver problemas de otimização onde o estado pode ser representado como um subconjunto de elementos. Frequentemente, essa abordagem é confundida com uma busca exaustiva (Brute Force), mas sua eficiência reside na memorização de estados e na trensição inteligente entre eles.

Identificando o Problema

Geralmente, um problema é candidato a Bitmask DP quando apresenta as seguintes características:

• O tamanho da entrada $n$ é pequeno, tipicamente $n \le 20$.
• O problema envolve decisões sequenciais onde cada escolha afeta as opções futuras.
• O estado pode ser compactado em um número inteiro, onde cada bit representa a presença (1) ou ausência (0) de um elemento no conjunto.

Fundamentos da Transição

A essência do Bitmask DP está na definição do estado, comumente representado como dp[mask][last_pos], onde mask é o conjunto atual de elementos processados e last_pos é o último elemento adicionado. A transição ocorre verificando se um novo elemento pode ser incluído no estado atual através de operações bit-a-bit (AND, OR, XOR).

Exemplo 1: Caminho Hamiltoniano Mínimo

O problema consiste em encontrar o caminho mais curto que visita cada nó exatamente uma vez, começando em um ponto fixo e terminando em outro.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_NODES = 20;
int dist[MAX_NODES][MAX_NODES];
int memo[1 << MAX_NODES][MAX_NODES];

int calcular_hamilton(int n) {
    memset(memo, 0x3f, sizeof(memo));
    memo[1][0] = 0; // Inicia no primeiro nó

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int atual = 0; atual < n; ++atual) {
            // Se o nó 'atual' não estiver na máscara, ignora
            if (!((mask >> atual) & 1)) continue;

            for (int anterior = 0; anterior < n; ++anterior) {
                // Verifica se o nó 'anterior' estava na máscara antes de adicionar 'atual'
                if (((mask ^ (1 << atual)) >> anterior) & 1) {
                    memo[mask][atual] = min(memo[mask][atual], 
                                            memo[mask ^ (1 << atual)][anterior] + dist[anterior][atual]);
                }
            }
        }
    }
    return memo[(1 << n) - 1][n - 1];
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> dist[i][j];

    cout << calcular_hamilton(n) << endl;
    return 0;
}

Nesta implementação, a máscara mask representa o conjunto de cidades visitadas. A transição busca o custo mínimo vindo de qualquer cidade anterior que já fazia parte do conjunto.

Exemplo 2: Pavimentação de Retângulos (Mondrian's Dream)

O desafio é preencher uma grade $N \times M$ com blocos $1 \times 2$. A chave aqui é focar no posicionamento das peças horizontais; as verticais serão preenchidas automaticamente nos espaços restantes, desde que esses espaços permitam (número par de células vazias consecutivas em uma coluna).

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

long long dp[12][1 << 11];
bool estado_valido[1 << 11];

void resolver() {
    int n, m;
    while (cin >> n >> m && (n || m)) {
        // Pré-processamento: estados que não deixam buracos ímpares para peças verticais
        for (int s = 0; s < (1 << n); ++s) {
            int zeros_consecutivos = 0;
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                if ((s >> i) & 1) {
                    if (zeros_consecutivos % 2 != 0) ok = false;
                    zeros_consecutivos = 0;
                } else {
                    zeros_consecutivos++;
                }
            }
            if (zeros_consecutivos % 2 != 0) ok = false;
            estado_valido[s] = ok;
        }

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for (int col = 1; col <= m; ++col) {
            for (int mask_atual = 0; mask_atual < (1 << n); ++mask_atual) {
                for (int mask_anterior = 0; mask_anterior < (1 << n); ++mask_anterior) {
                    // 1. Não pode haver sobreposição de peças horizontais entre colunas adjacentes
                    // 2. A união das peças deve permitir o encaixe de peças verticais
                    if ((mask_atual & mask_anterior) == 0 && estado_valido[mask_atual | mask_anterior]) {
                        dp[col][mask_atual] += dp[col - 1][mask_anterior];
                    }
                }
            }
        }
        cout << dp[m][0] << endl;
    }
}

int main() {
    resolver();
    return 0;
}

Análise da Lógica de Pavimentação

1. Peças Horizontais: Se um bit na mask_atual é 1, significa que um bloco $1 \times 2$ começa na coluna anterior e termina na atual.
2. Consistência: (mask_atual & mask_anterior) == 0 garante que uma peça horizontal vinda da coluna $j-2$ não colida com uma começando em $j-1$.
3. Espaço Vertical: estado_valido[mask_atual | mask_anterior] garante que, após posicionar as peças horizontais, os espaços vazios na coluna podem ser preanchidos por peças verticais $2 \times 1$.
4. Resultado: O valor em dp[m][0] representa todas as formas de preencher a grade até a última coluna sem deixar nenhuma peça "saindo" para fora do limite direito.