Visão Geral

A programação dinâmica com compressão de estado, também conhecida como DP com compressão, é uma técnica que utiliza as propriedades dos números binários para representar estados em um problema. Muitos problemas relacionados a tabuleiros, como campos ou tabuleiros de xadrez, utilizam esta abordagem.

Por exemplo, imagine um campo agrícola de tamanho n×n onde queremos plantar em algumas posições. Podemos representar cada linha do campo usando um número binário de comprimento n. Cada bit indica se uma posição está sendo usada (1) ou não (0).

Com isso, podemos descrever qualquer estado da linha usando apenas um número inteiro.

Operações de Bitwise

Para manipular esses estados, precisamos realizar operações bitwise. Aqui estão alguns exemplos:

1. x & y: Realiza uma operação AND entre os bits de x e y.
2. x | y: Realiza uma operação OR entre os bits de x e y.
3. x ^ y: Realiza uma operação XOR entre os bits de x e y.
4. x << k: Desloca os bits de x para a esquerda em k posições.
5. x >> k: Desloca os bits de x para a direita em k posições.

Essas operações são fundamentais para veriifcar ou modificar partes específicas de um estado.

Exemplo: Problema BFS + DP

Problema: Temos n lâmpadas e m botões. Cada botão pode alterar o estado de várias lâmpadas (ligar/desligar). Queremos saber o número mínimo de botões necessários para desligar todas as lâmpadas.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2048;
int n, m, initial_state;
bool visited[MAXN];
vector<int> button_effects[MAXN];

void bfs() {
    queue<pair<int, int>> q;
    q.push({initial_state, 0});
    visited[initial_state] = true;

    while (!q.empty()) {
        auto [current, steps] = q.front(); q.pop();
        if (current == 0) {
            cout << steps << endl;
            return;
        }
        for (int i = 1; i <= m; ++i) {
            int next_state = current ^ button_effects[i];
            if (!visited[next_state]) {
                visited[next_state] = true;
                q.push({next_state, steps + 1});
            }
        }
    }
    cout << "-1" << endl;
}

int main() {
    cin >> n >> m;
    initial_state = (1 << n) - 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < n; ++j) {
            int effect; cin >> effect;
            if (effect == 1) button_effects[i].push_back(1 << j);
            else if (effect == -1) button_effects[i].push_back(-(1 << j));
        }
    }
    bfs();
}

Exemplo: DP com Compressão

Problema: Em um campo de tamanho M×N, queremos plantar em algumas células sem que duas plantações sejam adjacentes.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000000;
int m, n, valid_states[4096], dp[19][4096];

bool is_valid(int state) {
    return !(state & (state << 1)) && !(state & (state >> 1));
}

int count_ones(int state) {
    int cnt = 0;
    while (state) { cnt += state & 1; state >>= 1; }
    return cnt;
}

int main() {
    cin >> m >> n;
    vector<string> grid(m);
    for (auto &s : grid) cin >> s;

    int max_state = (1 << n) - 1;
    for (int s = 0; s <= max_state; ++s)
        if (is_valid(s)) valid_states[s] = true;

    for (int s = 0; s <= max_state; ++s)
        if (valid_states[s]) {
            bool ok = true;
            for (int j = 0; j < n; ++j)
                if ((s & (1 << j)) && grid[0][j] == '0') ok = false;
            if (ok) dp[0][s] = 1;
        }

    for (int i = 1; i < m; ++i)
        for (int s = 0; s <= max_state; ++s)
            if (valid_states[s]) {
                for (int prev = 0; prev <= max_state; ++prev)
                    if (!(s & prev) && valid_states[prev])
                        dp[i][s] = (dp[i][s] + dp[i - 1][prev]) % MOD;
            }

    long long result = 0;
    for (int s = 0; s <= max_state; ++s) result = (result + dp[m - 1][s]) % MOD;
    cout << result << endl;
}