Ao desenvolver algoritmos complexos, especialmente em Programação Dinâmica (PD), a visualização e gestão dos estados são cruciais. Este artigo explora duas abordagens avançadas para a estruturação de soluções de PD: a modelagem com Máquinas de Estados Finitos e a Compressão de Estado (Bitmask DP), apresentando exemplos detalhados para cada uma.
Modelagem com Máquinas de Estados Finitos
Uma Máquina de Estados Finita (MEF), ou Finite-state machine (FSM), é um modelo matemático que descreve o comportamento de um sistema com um número finito de estados, as transições entre esses estados e as ações associadas. Na Programação Dinâmica, aplicamos este cocneito para representar as diferentes "situações" ou "contextos" que um problema pode ter em cada etapa. Isso nos permite definir as transições entre os estados de forma lógica e sistemática, facilitando a construção da relação de recorrência da PD.
Vamos explorar essa abordagem através de problemas clássicos:
Exemplo 1: O Ladrão Habilidoso
Um ladrão experiente planeja roubar lojas em uma rua. Existem N lojas, cada uma com uma certa quantia de dinheiro. Um sistema de alarme é ativado se duas lojas adjacentes forem roubadas simultaneamente. O ladrão, avesso a riscos, quer maximizar o dinheiro roubado sem ativar o alarme. Qual é a quantia máxima que ele pode obter?
Entrada: A primeira linha contém um inteiro T (número de casos de teste). Para cada caso: a primeira linha tem N (número de lojas), a segunda linha tem N inteiros (dinheiro em cada loja).
Saída: Para cada caso, a quantia máxima de dinheiro.
Restrições: 1 ≤ T ≤ 50, 1 ≤ N ≤ 10^5, dinheiro em cada loja ≤ 1000.
Para este problema, podemos definir dois estados para cada loja i:
dp[i][0]: O lucro máximo obtido até a lojai, não roubando a lojai.dp[i][1]: O lucro máximo obtido até a lojai, roubando a lojai.
As transições de estado seriam:
- Para
dp[i][0](não roubar a lojai): Podemos ter chegado aqui de duas maneiras na lojai-1: ou não roubamosi-1, ou roubamosi-1. O lucro máximo será o maior entredp[i-1][0]edp[i-1][1]. - Para
dp[i][1](roubar a lojai): Para roubar a lojai, a lojai-1não pode ter sido roubada. Então, somamos o dinheiro da lojaiadp[i-1][0].
Podemos visualizar isso com um diagrama de estados:
Implementação em C++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_LOJAS = 100010;
int num_lojas;
int dinheiro_nas_casas[MAX_LOJAS];
int dp_lucro_maximo[MAX_LOJAS][2]; // [0] = nao roubar, [1] = roubar
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &num_lojas);
for (int i = 1; i <= num_lojas; i++) {
scanf("%d", &dinheiro_nas_casas[i]);
}
// Casos base: dp_lucro_maximo[0][0] = 0, dp_lucro_maximo[0][1] = 0
// (implícito pois arrays globais/estáticos são inicializados com zero)
for (int i = 1; i <= num_lojas; i++) {
// Se nao roubarmos a loja 'i', podemos ter vindo de qualquer estado da loja 'i-1'
dp_lucro_maximo[i][0] = max(dp_lucro_maximo[i-1][0], dp_lucro_maximo[i-1][1]);
// Se roubarmos a loja 'i', a loja 'i-1' nao poderia ter sido roubada
dp_lucro_maximo[i][1] = dp_lucro_maximo[i-1][0] + dinheiro_nas_casas[i];
}
printf("%d\n", max(dp_lucro_maximo[num_lojas][0], dp_lucro_maximo[num_lojas][1]));
}
return 0;
}
Exemplo 2: Compra e Venda de Ações (com K transações)
Dado um array de preços de ações, onde precos[i] é o preço no dia i. Projete um algoritmo para calcular o lucro máximo que você pode obter, realizando no máximo k transações. Você não pode participar de várias transações simultaneamente (deve vender antes de comprar novamente).
Entrada: A primeira linha contém N (dias) e k (transações máximas). A segunda linha contém N inteiros (preços das ações).
Saída: O lucro máximo.
Restrições: 1 ≤ N ≤ 10^5, 1 ≤ k ≤ 100.
Para este problema, precisamos considerar o dia atual, o número de transações já realizadas e se estamos segurando uma ação. Os estados podem ser definidos como:
dp[d][t][0]: O lucro máximo no diad, tendo realizadottransações, e não possuindo ações.dp[d][t][1]: O lucro máximo no diad, tendo realizadottransações, e possuindo uma ação.
O diagrama de estados nos ajuda a visualizar as transições:
As transições seriam:
-
Para
dp[d][t][0](não possuir ações no diad):- Podemos ter vindo de
dp[d-1][t][0](não tínhamos ações no dia anterior e não fizemos nada). - Ou podemos ter vindo de
dp[d-1][t][1]e vendemos a ação no diad(adicionandoprecos[d]).
Portanto,
dp[d][t][0] = max(dp[d-1][t][0], dp[d-1][t][1] + precos[d]). - Podemos ter vindo de
-
Para
dp[d][t][1](possuir uma ação no diad):- Podemos ter vindo de
dp[d-1][t][1](já possuíamos uma ação e não fizemos nada). - Ou podemos ter vindo de
dp[d-1][t-1][0]e compramos uma ação no diad(subtraindoprecos[d]e usando uma transação).
Portanto,
dp[d][t][1] = max(dp[d-1][t][1], dp[d-1][t-1][0] - precos[d]). - Podemos ter vindo de
A inicialização é crucial: -INF para estados inacessíveis e 0 para o estado inicial de não possuir ações com 0 transações.
Implementação em C++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_DIAS = 100010, MAX_TRANSACOES = 110, INF = 0x3f3f3f3f;
int num_dias, num_transacoes_max;
int precos_acoes[MAX_DIAS];
int dp_lucro[MAX_DIAS][MAX_TRANSACOES][2]; // [dia][transacoes][0=sem acoes, 1=com acoes]
int main() {
scanf("%d%d", &num_dias, &num_transacoes_max);
for (int i = 1; i <= num_dias; i++) {
scanf("%d", &precos_acoes[i]);
}
// Inicializa dp com -INF para indicar estados inacessíveis
memset(dp_lucro, -0x3f, sizeof dp_lucro);
// Para 0 transacoes e 0 dias, sem acoes, o lucro e 0
for (int i = 0; i <= num_dias; i++) {
dp_lucro[i][0][0] = 0;
}
for (int dia = 1; dia <= num_dias; dia++) {
for (int trans = 1; trans <= num_transacoes_max; trans++) {
// Nao possuir acoes no dia 'dia', com 'trans' transacoes
// 1. Nao possuia e nao fez nada no dia 'dia'
// 2. Possuia e vendeu no dia 'dia'
dp_lucro[dia][trans][0] = max(dp_lucro[dia-1][trans][0], dp_lucro[dia-1][trans][1] + precos_acoes[dia]);
// Possuir acoes no dia 'dia', com 'trans' transacoes
// 1. Possuia e nao fez nada no dia 'dia'
// 2. Nao possuia (com 'trans-1' transacoes) e comprou no dia 'dia'
dp_lucro[dia][trans][1] = max(dp_lucro[dia-1][trans][1], dp_lucro[dia-1][trans-1][0] - precos_acoes[dia]);
}
}
int lucro_max = 0;
for (int trans = 0; trans <= num_transacoes_max; trans++) {
lucro_max = max(lucro_max, dp_lucro[num_dias][trans][0]);
}
printf("%d\n", lucro_max);
return 0;
}
Exemplo 3: Compra e Venda de Ações (com período de carência)
Dado um array de preços de ações, calcule o lucro máximo. As restrições são:
- Não pode participar de várias transações simultaneamente (deve vender antes de comprar).
- Após vender uma ação, você não pode comprar outra no dia seguinte (período de carência de 1 dia).
Entrada: N (dias). N inteiros (preços das ações).
Saída: O lucro máximo.
Restrições: 1 ≤ N ≤ 10^5.
Devido ao período de carência, expandimos os estados para o caso de não possuir ações:
dp[d][0]: Lucro máximo no diad, possuindo uma ação (comprou no diadou antes).dp[d][1]: Lucro máximo no diad, acabou de vender uma ação (e está em carência).dp[d][2]: Lucro máximo no diad, não possuindo ações e não estando em carência (pode comprar).
O diagrama de estados detalha as transições:
As transições seriam:
-
Para
dp[d][0](possuir ação):- Podemos ter vindo de
dp[d-1][0](já possuíamos). - Ou podemos ter vindo de
dp[d-1][2]e comprado no diad(não estávamos em carência).
dp[d][0] = max(dp[d-1][0], dp[d-1][2] - cotacoes[d]). - Podemos ter vindo de
-
Para
dp[d][1](acabou de vender):- Só podemos ter vindo de
dp[d-1][0]e vendido no diad.
dp[d][1] = dp[d-1][0] + cotacoes[d]. - Só podemos ter vindo de
-
Para
dp[d][2](não possuir, não em carência):- Podemos ter vindo de
dp[d-1][2](já estávamos nesse estado). - Ou podemos ter vindo de
dp[d-1][1](saímos da carência).
dp[d][2] = max(dp[d-1][2], dp[d-1][1]). - Podemos ter vindo de
Implementação em C++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_DIAS = 100010, INF = 0x3f3f3f3f;
int num_dias;
int cotacoes[MAX_DIAS];
int dp_estado[MAX_DIAS][3]; // [0]=com acoes, [1]=acabou de vender, [2]=descanso
int main() {
scanf("%d", &num_dias);
for (int i = 1; i <= num_dias; i++) {
scanf("%d", &cotacoes[i]);
}
// Inicializacao:
// No dia 0 (antes do primeiro dia de negociacao),
// nao podemos ter acoes nem ter acabado de vender.
dp_estado[0][0] = dp_estado[0][1] = -INF;
// Podemos estar em estado de descanso com 0 lucro.
dp_estado[0][2] = 0;
for (int dia = 1; dia <= num_dias; dia++) {
// Estado 0: Comprando ou mantendo acao
// Maximo entre:
// 1. Manter a acao que ja tinha no dia anterior
// 2. Comprar uma acao hoje, vindo do estado de descanso (nao em carencia)
dp_estado[dia][0] = max(dp_estado[dia-1][0], dp_estado[dia-1][2] - cotacoes[dia]);
// Estado 1: Acabou de vender acao
// So pode vir de ter uma acao no dia anterior e vender hoje
dp_estado[dia][1] = dp_estado[dia-1][0] + cotacoes[dia];
// Estado 2: Descanso (nao tem acao, nao em carencia, pode comprar)
// Maximo entre:
// 1. Ja estava em descanso no dia anterior
// 2. Saiu do estado de "acabou de vender" (carecia no dia anterior, mas hoje nao)
dp_estado[dia][2] = max(dp_estado[dia-1][2], dp_estado[dia-1][1]);
}
// O lucro maximo pode estar no estado de ter acabado de vender ou estar em descanso no ultimo dia
printf("%d\n", max(dp_estado[num_dias][1], dp_estado[num_dias][2]));
return 0;
}
Exemplo 4: Design de Senhas
Você precisa projetar uma senha S que atenda aos seguintes requisitos:
- O comprimento de
SéN. Scontém apenas letras minúsculas do alfabeto inglês.Snão contém a substringT.
Quantas senhas diferentes satisfazem esses requisitos? A resposta pode ser muito grande, então imprima o resultado módulo 10^9 + 7.
Entrada: N (comprimento da senha). T (substring a ser evitada).
Saída: O número total de senhas válidas módulo 10^9 + 7.
Restrições: 1 ≤ N ≤ 50, 1 ≤ |T| ≤ N.
Este problema pode ser resolvido usando PD com um autômato para correspondência de padrões (similar ao algoritmo KMP). Definimos:
dp[i][j]: O número de senhas válidas de comprimentoi, onde o sufixo mais longo da senha que também é um prefixo deTtem comprimentoj.
O estado j representa o "quão perto" estamos de formar a substring proibida T. Precisamos precomputar as transições do autômato KMP para cada caractere possível. O diagrama de estados ilustra isso:
O array kmp_proximo[j] armazena o comprimento do maior prefixo de T que também é um sufixo de T[1...j]. Para cada estado j (comprimento do prefixo de T que já foi correspondido) e para cada novo caractere k que adicionamos:
- Encontramos o próximo estado
uno autômato KMP. - Se
ufor menor que o comprimento deT(ou seja, não formamos a string proibida), então atualizamosdp[i+1][u].
Implementação em C++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_LEN = 55, MOD = 1e9 + 7;
int len_senha, len_padrao;
char padrao_restrito[MAX_LEN];
int kmp_proximo[MAX_LEN]; // array para a funcao de falha KMP
int dp_contagem[MAX_LEN][MAX_LEN]; // dp_contagem[i][j]: senhas de comprimento i, com prefixo T de comprimento j
int main() {
cin >> len_senha >> (padrao_restrito + 1);
len_padrao = strlen(padrao_restrito + 1);
// Precomputa o array kmp_proximo para o padrao_restrito
for (int i = 2, j = 0; i <= len_padrao; i++) {
while (j && padrao_restrito[i] != padrao_restrito[j + 1]) j = kmp_proximo[j];
if (padrao_restrito[i] == padrao_restrito[j + 1]) j++;
kmp_proximo[i] = j;
}
dp_contagem[0][0] = 1; // 1 maneira de ter uma string vazia com 0 de match
// Itera sobre o comprimento da senha
for (int i = 0; i < len_senha; i++) {
// Itera sobre o estado de match KMP atual
for (int j = 0; j < len_padrao; j++) {
// Se dp_contagem[i][j] for 0, nao ha maneiras de chegar a esse estado, entao pula
if (dp_contagem[i][j] == 0) continue;
// Tenta adicionar cada caractere possivel ('a' a 'z')
for (char prox_char_val = 'a'; prox_char_val <= 'z'; prox_char_val++) {
int estado_kmp_atual = j;
// Simula a transicao do automato KMP
while (estado_kmp_atual && prox_char_val != padrao_restrito[estado_kmp_atual + 1]) {
estado_kmp_atual = kmp_proximo[estado_kmp_atual];
}
if (prox_char_val == padrao_restrito[estado_kmp_atual + 1]) {
estado_kmp_atual++;
}
// Se o novo estado_kmp_atual nao corresponde a um match completo do padrao
if (estado_kmp_atual < len_padrao) {
dp_contagem[i + 1][estado_kmp_atual] = (dp_contagem[i + 1][estado_kmp_atual] + dp_contagem[i][j]) % MOD;
}
}
}
}
int resultado_final = 0;
// Soma todas as maneiras de formar uma senha de comprimento N que nao contenha o padrao
for (int i = 0; i < len_padrao; i++) {
resultado_final = (resultado_final + dp_contagem[len_senha][i]) % MOD;
}
cout << resultado_final << endl;
return 0;
}
Exemplo 5: Reparação de DNA
Biólogos desenvolveram uma técnica para reparar segmentos de DNA que contêm doenças genéticas. O DNA é uma sequência de caracteres 'A', 'G', 'C', 'T'. A técnica consiste em modificar o mínimo de caracteres na sequência de DNA dada para que ela não contenha nenhum dos "fragmentos patogênicos" fornecidos. Encontre o número mínimo de modificações.
Entrada: Múltiplos casos de teste. Cada caso começa com N (número de fragmentos patogênicos). Seguem N linhas com os fragmentos. Depois, uma linha com a sequência de DNA a ser reparada. O caso 0 termina a entrada.
Saída: Para cada caso, "Case x: y", onde x é o número do caso e y é o mínimo de modificações. Se for impossível, y é "-1".
Restrições: 1 ≤ N ≤ 50, comprimento de fragmento ≤ 20. Comprimento do DNA a reparar ≤ 1000.
Para este problema, usaremos um autômato Aho-Corasick para detectar múltiplos padrões patogênicos e PD. O autômato nos permite encontrar todas as ocorrências de qualquer um dos padrões em tempo linear. Os estados da PD serão:
dp[i][j]: O número mínimo de modificações para os primeirosicaracteres da sequência de DNA alvo, onde o autômato Aho-Corasick está no estadoj.
A transição ocorre ao processar o (i+1)-ésimo caractere da sequência alvo. Para cada estado j do autômato e para cada possível caractere ('A', 'G', 'C', 'T') que podemos colocar na posição i+1:
- Calculamos o custo de modificação (0 se o caractere for igual, 1 se for diferente).
- Encontramos o próximo estado
pno autômato Aho-Corasick. - Se o estado
pnão indica que um padrão patogênico foi encontrado (termina_padrao_nocivo[p] == 0), atualizamosdp[i+1][p].
Implementação em C++
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX_NODES_TRIE = 50 * 20 + 5; // N * comprimento max padrao + 1
const int MAX_DNA_LEN = 1010;
int num_padroes, len_dna_alvo;
int trie_nodes[MAX_NODES_TRIE][4]; // Trie: 0=A, 1=T, 2=G, 3=C
bool termina_padrao_nocivo[MAX_NODES_TRIE]; // Indica se um padrao termina aqui
int trie_idx; // Contador de nos na Trie
int link_falha[MAX_NODES_TRIE]; // Links de falha (KMP next)
char seq_dna_alvo[MAX_DNA_LEN];
int dp_min_mudancas[MAX_DNA_LEN][MAX_NODES_TRIE]; // dp[i][j]: min mudancas para prefixo i, estado j na Aho-Corasick
// Mapeia caractere para indice
int get_char_idx(char c) {
if (c == 'A') return 0;
if (c == 'T') return 1;
if (c == 'G') return 2;
return 3; // 'C'
}
// Insere um padrao na Trie
void insert_pattern(const char* pattern) {
int p = 0;
for (int i = 0; pattern[i]; i++) {
int t = get_char_idx(pattern[i]);
if (trie_nodes[p][t] == 0) trie_nodes[p][t] = ++trie_idx;
p = trie_nodes[p][t];
}
termina_padrao_nocivo[p] = true;
}
// Constroi o automato Aho-Corasick (links de falha)
void build_aho_corasick() {
queue<int> q_bfs;
for (int i = 0; i < 4; i++) {
if (trie_nodes[0][i]) {
q_bfs.push(trie_nodes[0][i]);
}
}
while (!q_bfs.empty()) {
int u = q_bfs.front();
q_bfs.pop();
for (int i = 0; i < 4; i++) {
int v = trie_nodes[u][i];
if (!v) { // Se nao ha transicao direta, usa o link de falha
trie_nodes[u][i] = trie_nodes[link_falha[u]][i];
} else { // Se ha transicao direta, constroi o link de falha para o proximo no
link_falha[v] = trie_nodes[link_falha[u]][i];
// Propaga a informacao de padrao nocivo para links de falha
termina_padrao_nocivo[v] |= termina_padrao_nocivo[link_falha[v]];
q_bfs.push(v);
}
}
}
}
int main() {
int case_num = 1;
while (scanf("%d", &num_padroes) && num_padroes != 0) {
memset(trie_nodes, 0, sizeof trie_nodes);
memset(termina_padrao_nocivo, 0, sizeof termina_padrao_nocivo);
memset(link_falha, 0, sizeof link_falha);
trie_idx = 0;
char current_pattern[25];
for (int i = 0; i < num_padroes; i++) {
scanf("%s", current_pattern);
insert_pattern(current_pattern);
}
build_aho_corasick();
scanf("%s", seq_dna_alvo + 1); // 1-indexed
len_dna_alvo = strlen(seq_dna_alvo + 1);
memset(dp_min_mudancas, 0x3f, sizeof dp_min_mudancas); // Inicializa com infinito
dp_min_mudancas[0][0] = 0; // 0 mudancas para uma string vazia no estado 0 da Trie
// DP para cada caractere na sequencia de DNA alvo
for (int i = 0; i < len_dna_alvo; i++) {
for (int j = 0; j <= trie_idx; j++) { // Itera sobre todos os estados da Aho-Corasick
if (dp_min_mudancas[i][j] == 0x3f3f3f3f) continue; // Pula estados inatingiveis
for (int k = 0; k < 4; k++) { // Tenta colocar cada um dos 4 caracteres (A, T, G, C)
int custo_mudanca = (get_char_idx(seq_dna_alvo[i + 1]) != k); // 1 se mudar, 0 se igual
int proximo_estado = trie_nodes[j][k];
// Se o proximo estado nao resulta em um padrao nocivo
if (!termina_padrao_nocivo[proximo_estado]) {
dp_min_mudancas[i + 1][proximo_estado] = min(dp_min_mudancas[i + 1][proximo_estado], dp_min_mudancas[i][j] + custo_mudanca);
}
}
}
}
int min_total_mudancas = 0x3f3f3f3f;
for (int i = 0; i <= trie_idx; i++) {
min_total_mudancas = min(min_total_mudancas, dp_min_mudancas[len_dna_alvo][i]);
}
if (min_total_mudancas == 0x3f3f3f3f) min_total_mudancas = -1; // Impossivel reparar
printf("Case %d: %d\n", case_num++, min_total_mudancas);
}
return 0;
}
Programação Dinâmica com Compressão de Estado (Bitmask DP)
A Programação Dinâmica com Compressão de Estado, frequentemente chamada de Bitmask DP, emprega as propriedades do sistema binário para representar estados de forma eficiente. É uma técnica comum em problemas de tabuleiro e combinatória, muitas vezes usada em conjunto com Busca em Largura (BFS) ou outras abordagens de PD. A ideia central é codificar o estado de um conjunto de elementos (como células em uma linha de um tabuleiro) em um único número inteiro, onde cada bit representa uma propriedade ou a presença/ausência de um elemento. Por exemplo, em um tabuleiro de N colunas, uma configuração para uma linha pode ser representada por um número binário de N bits, onde '1' indica uma posição ocupada e '0' uma posição livre. Essa abordagem permite iterar sobre todas as 2^N configurações possíveis. Embora o número de estados possa parecer grande (2^N), muitos problemas permitem a eliminação de estados inválidos, reduzindo significativamente o espaço de busca e a complexidade. A manipulação desses estados comprimidos é feita através de operações bit a bit (bit-shift, AND, OR, XOR), que são essenciais para construir as transições da PD.
Exemplo de estado para uma linha de 9 colunas:
| Coluna | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Binário | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| Ocupado? | ✔️ | ❌ | ❌ | ❌ | ✔️ | ✔️ | ❌ | ✔️ | ✔️ |
Este padrão de ocupação (100011011 em binário) pode ser representado por um único número inteiro. Essa representação torna as transições de estado mais concisas.
Exemplo 6: Posicionando Reis no Tabuleiro
Em um tabuleiro de xadrez N×N, coloque K reis de forma que nenhum rei ataque outro. Um rei podde atacar os 8 quadrados adjacentes (horizontal, vertical e diagonalmente). Encontre o número total de maneiras de posicionar os reis.
Entrada: N (tamanho do tabuleiro), K (número de reis).
Saída: O número total de arranjos válidos.
Restrições: 1 ≤ N ≤ 10, 0 ≤ K ≤ N^2.
Para este problema, podemos usar Bitmask DP linha por linha. Os estados são:
dp[linha][reis_colocados][mascara_linha]: Número de maneiras de colocarreis_colocadosreis nas primeiraslinhalinhas, com a configuração da linhalinhasendomascara_linha.
As condições para um posicionamento válido são:
- Nenhum rei pode ser adjacente a outro na mesma linha (
(mascara & (mascara << 1)) == 0). - Nenhum rei pode ser adjacente a outro na linha anterior (
(mascara_atual & mascara_anterior) == 0). - Nenhum rei pode ser adjacente diagonalmente à linha anterior (
(mascara_atual & (mascara_anterior << 1)) == 0e(mascara_atual & (mascara_anterior >> 1)) == 0).
Implementação em C++
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int MAX_N = 12, MAX_ESTADOS_LINHA = 1 << 10, MAX_K_REIS = 110;
int num_linhas_tabuleiro, num_reis_a_colocar;
vector<int> config_validas_linha; // Armazena todas as mascaras validas para uma linha
int contagem_reis[MAX_ESTADOS_LINHA]; // contagem_reis[mask] = numero de reis na mascara
vector<int> adjacencias_validas[MAX_ESTADOS_LINHA]; // adjacencias_validas[idx_a] = indices das mascaras b validas para linha anterior
LL dp_arranjos[MAX_N][MAX_K_REIS][MAX_ESTADOS_LINHA];
// dp_arranjos[i][j][k]: numero de maneiras de colocar j reis nas i primeiras linhas,
// com a i-esima linha tendo a configuracao k
// Verifica se uma configuracao de reis em uma linha e valida (sem reis adjacentes horizontalmente)
bool eh_config_linha_valida(int configuracao) {
for (int i = 0; i < num_linhas_tabuleiro; i++) {
if ((configuracao >> i & 1) && (configuracao >> (i + 1) & 1)) {
return false;
}
}
return true;
}
// Conta o numero de reis em uma configuracao
int contar_bits(int configuracao) {
int res = 0;
for (int i = 0; i < num_linhas_tabuleiro; i++) {
res += (configuracao >> i & 1);
}
return res;
}
int main() {
cin >> num_linhas_tabuleiro >> num_reis_a_colocar;
// 1. Gerar todas as configuracoes validas para uma unica linha
for (int i = 0; i < (1 << num_linhas_tabuleiro); i++) {
if (eh_config_linha_valida(i)) {
config_validas_linha.push_back(i);
contagem_reis[i] = contar_bits(i);
}
}
// 2. Precomputar transicoes validas entre duas linhas consecutivas
for (int i = 0; i < config_validas_linha.size(); i++) {
for (int j = 0; j < config_validas_linha.size(); j++) {
int config_a = config_validas_linha[i]; // Configuracao da linha atual
int config_b = config_validas_linha[j]; // Configuracao da linha anterior
// Condicoes de nao ataque entre linhas adjacentes
// - Nao pode haver reis na mesma coluna (a & b == 0)
// - Nao pode haver reis na diagonal superior esquerda/direita (check(a | b))
// Essa funcao 'check' na verdade verifica se nao ha dois bits adjacentes DENTRO
// da MASCARA RESULTANTE, que ja cobre a condicao diagonal aqui pois a|b
// representa a uniao dos reis nas duas linhas.
if (!((config_a & config_b) || (config_a & (config_b << 1)) || (config_a & (config_b >> 1)))) {
adjacencias_validas[i].push_back(j);
}
}
}
// dp_arranjos[linha][reis_colocados][mascara_linha_atual_idx]
// O estado inicial e antes da primeira linha (linha 0), com 0 reis e configuracao 0 (vazia), 1 maneira.
dp_arranjos[0][0][0] = 1;
// O loop vai ate num_linhas_tabuleiro, mas o problema envolve n-1 transicoes.
// Para simplificar o indice e pegar o resultado final f[n][m][0],
// geralmente se usa n+1 linhas na DP para que a ultima linha possa ser tratada de forma consistente.
for (int i = 1; i <= num_linhas_tabuleiro + 1; i++) { // Iterar sobre as linhas
for (int j = 0; j <= num_reis_a_colocar; j++) { // Iterar sobre o numero de reis ja colocados
for (int atual_idx = 0; atual_idx < config_validas_linha.size(); atual_idx++) { // Configuracao da linha atual
int config_atual = config_validas_linha[atual_idx];
int reis_linha_atual = contagem_reis[config_atual];
if (j >= reis_linha_atual) { // Se podemos colocar reis_linha_atual reis nesta configuracao
// Iterar sobre as configuracoes validas da linha anterior
for (int anterior_idx : adjacencias_validas[atual_idx]) {
dp_arranjos[i][j][atual_idx] += dp_arranjos[i - 1][j - reis_linha_atual][anterior_idx];
}
}
}
}
}
// O resultado final e o numero de maneiras de colocar 'num_reis_a_colocar' reis em 'num_linhas_tabuleiro' linhas,
// com a ultima linha (linha num_linhas_tabuleiro+1, mas o estado aqui e [num_linhas_tabuleiro+1][num_reis_a_colocar][0])
// tendo a configuracao 0 (vazia, para garantir que nao ha reis na linha N+1 afetando N).
// Ou seja, f[num_linhas_tabuleiro][num_reis_a_colocar][qualquer_config_valida] mas somado.
// Usando [num_linhas_tabuleiro+1][num_reis_a_colocar][0] eh um truque comum para problemas onde a contagem final
// deve ser de "maneiras de terminar", onde a ultima linha vazia atua como um estado final.
cout << dp_arranjos[num_linhas_tabuleiro + 1][num_reis_a_colocar][0] << endl;
return 0;
}
Exemplo 7: Plantio de Milho
A terra do Fazendeiro João consiste em uma grade M×N. Ele quer plantar milho. Algumas terras são inférteis e não podem ser plantadas. Além disso, terras adjacentes (com borda comum) não podem ser plantadas simultaneamente. Calcule o número total de maneiras de plantar milho (nenhum milho plantado também é uma maneira).
Entrada: M (linhas), N (colunas). Seguem M linhas com N inteiros (0=infértil, 1=fértil).
Saída: O número total de métodos de plantio módulo 10^8.
Restrições: 1 ≤ M, N ≤ 12.
Este problema também utiliza Bitmask DP linha por linha. Os estados são:
dp[linha][mascara_linha]: O número de maneiras de plantar milho nas primeiraslinhalinhas, com a configuração da linhalinhasendomascara_linha.
As condições para uma configuração mascara_linha na linha i ser válida são:
- Não pode haver plantas adjacentes horizontalmente na mesma linha.
- Não pode haver plantas em terrenos inférteis.
- Não pode haver plantas na linha
iadjacentes a plantas na linhai-1.
Implementação em C++
#include <cstring>
#include <iostream>
#lt;algorithm>
#include <vector>
using namespace std;
const int MAX_DIM = 14, MAX_MASK = 1 << 12, MOD = 1e8;
int num_linhas, num_colunas;
int terreno_infertil[MAX_DIM]; // terreno_infertil[i] = mascara de bits para celulas inferteis na linha i
vector<int> config_validas_linha; // Armazena todas as mascaras validas para uma linha
vector<int> transicoes_linha[MAX_MASK]; // transicoes_linha[idx_atual] = indices das mascaras validas para linha anterior
int dp_plantio[MAX_DIM][MAX_MASK];
// dp_plantio[i][j]: numero de maneiras de plantar ate a linha i, com a linha i tendo a configuracao j (mascara de bits)
// Verifica se uma configuracao de milho em uma linha e valida (sem adjacencias horizontais)
bool eh_config_linha_valida(int configuracao) {
for (int i = 0; i + 1 < num_colunas; i++) {
if ((configuracao >> i & 1) && (configuracao >> (i + 1) & 1)) {
return false;
}
}
return true;
}
int main() {
cin >> num_linhas >> num_colunas;
// Converte o mapa de terreno para mascaras de bits de celulas inferteis
for (int i = 1; i <= num_linhas; i++) {
for (int j = 0; j < num_colunas; j++) {
int tipo_celula;
cin >> tipo_celula;
if (tipo_celula == 0) { // Se infertil
terreno_infertil[i] |= (1 << j); // Marca a posicao como infertil
}
}
}
// 1. Gerar todas as configuracoes validas para uma unica linha (sem adjacencias horizontais)
for (int i = 0; i < (1 << num_colunas); i++) {
if (eh_config_linha_valida(i)) {
config_validas_linha.push_back(i);
}
}
// 2. Precomputar transicoes validas entre duas linhas consecutivas
// transicoes_linha[idx_config_atual] armazena os indices das mascaras validas para a linha anterior
// que podem preceder config_validas_linha[idx_config_atual]
for (int i = 0; i < config_validas_linha.size(); i++) {
for (int j = 0; j < config_validas_linha.size(); j++) {
int config_a = config_validas_linha[i]; // Configuracao da linha atual
int config_b = config_validas_linha[j]; // Configuracao da linha anterior
// Se nao houver sobreposicao de plantas entre as duas linhas (verticalmente adjacentes)
if (!(config_a & config_b)) {
transicoes_linha[i].push_back(j);
}
}
}
// O estado inicial e antes da primeira linha (linha 0), 1 maneira de ter uma linha vazia (config 0)
dp_plantio[0][0] = 1;
// O loop vai ate num_linhas, mas o problema envolve n-1 transicoes.
// Para simplificar o indice e pegar o resultado final,
// geralmente se usa n+1 linhas na DP para que a ultima linha possa ser tratada de forma consistente.
for (int i = 1; i <= num_linhas + 1; i++) { // Iterar sobre as linhas
for (int atual_idx = 0; atual_idx < config_validas_linha.size(); atual_idx++) { // Configuracao da linha atual
int config_atual = config_validas_linha[atual_idx];
// Se a configuracao atual tiver plantas em terreno infertil, e invalida
if (!(config_atual & terreno_infertil[i])) {
// Iterar sobre as configuracoes validas da linha anterior
for (int anterior_idx : transicoes_linha[atual_idx]) {
dp_plantio[i][atual_idx] = (dp_plantio[i][atual_idx] + dp_plantio[i - 1][anterior_idx]) % MOD;
}
}
}
}
// O resultado final e o numero de maneiras de plantar em N linhas,
// com a ultima linha (num_linhas + 1) tendo a configuracao 0 (vazia),
// para garantir que nao ha plantas na ultima linha que possam ter interagido com uma linha N+1 inexistente.
cout << dp_plantio[num_linhas + 1][0] << endl;
return 0;
}
Exemplo 8: Posicionamento de Artilharia
Generais querem posicionar unidades de artilharia em um mapa de grade N×M. Cada célula pode ser montanha ('H') ou planície ('P'). Uma unidade de artilharia pode ser colocada apenas em planícies. O alcance de ataque de uma unidade é de duas células horizontalmente e duas células verticalmente. Quaisquer duas unidades de artilharia não podem se atacar. Encontre o número máximo de unidades que podem ser posicionadas.
Entrada: N (linhas), M (colunas). Seguem N linhas com M caracteres ('P' ou 'H').
Saída: O número máximo de uniddaes de artilharia.
Restrições: N ≤ 100, M ≤ 10.
Este é um problema de Bitmask DP com dependência de três linhas (a linha atual e as duas anteriores). Os estados serão:
dp[linha][mascara_linha_atual][mascara_linha_anterior]: O número máximo de unidades de artilharia colocadas até alinhaatual, com alinhaatual tendo a configuraçãomascara_linha_atuale alinha-1tendo a configuraçãomascara_linha_anterior.
Para otimização de espaço, podemos usar dp[linha & 1] para alternar entre as linhas. As condições para um posicionamento válido são:
- Nenhuma unidade pode ser colocada em 'H'.
- Nenhuma unidade pode ser adjacente horizontalmente (duas posições).
- Nenhuma unidade na
linhapode atacar unidades nalinha-1oulinha-2.
Implementação em C++
#include <cstring>
#include <iostream>
#lt;algorithm>
#include <vector>
using namespace std;
const int MAX_COLUNAS = 10, MAX_CONFIGURACOES = 1 << 10; // M <= 10
const int MAX_LINHAS = 100;
int num_linhas, num_colunas;
int mapa_terreno[MAX_LINHAS + 5]; // mapa_terreno[i] = mascara de bits de 'H' (montanhas) na linha i
int dp_max_canhoes[2][MAX_CONFIGURACOES][MAX_CONFIGURACOES];
// dp_max_canhoes[linha_atual % 2][config_linha_atual][config_linha_anterior]
vector<int> posicoes_validas; // Todas as mascaras validas para uma linha (sem ataques internos)
int contagem_canhoes[MAX_CONFIGURACOES]; // contagem_canhoes[mask] = numero de canhoes na mascara
// Verifica se uma configuracao de canhoes em uma linha e valida (sem ataques internos na horizontal)
bool eh_config_valida(int configuracao) {
for (int i = 0; i < num_colunas; i++) {
// Verifica se ha 1s em posicoes i e i+1 ou i e i+2
if ((configuracao >> i & 1) && ((configuracao >> (i + 1) & 1) || (configuracao >> (i + 2) & 1))) {
return false;
}
}
return true;
}
// Conta o numero de canhoes em uma configuracao
int contar_bits(int configuracao) {
int res = 0;
for (int i = 0; i < num_colunas; i++) {
if (configuracao >> i & 1) res++;
}
return res;
}
int main() {
cin >> num_linhas >> num_colunas;
// Converte o mapa de terreno para mascaras de bits de montanhas
for (int i = 1; i <= num_linhas; i++) {
for (int j = 0; j < num_colunas; j++) {
char c;
cin >> c;
if (c == 'H') { // Se montanha
mapa_terreno[i] |= (1 << j); // Marca a posicao como montanha
}
}
}
// 1. Gerar todas as configuracoes validas para uma unica linha (sem ataques internos)
for (int i = 0; i < (1 << num_colunas); i++) {
if (eh_config_valida(i)) {
posicoes_validas.push_back(i);
contagem_canhoes[i] = contar_bits(i);
}
}
// DP: Iterar sobre as linhas
for (int i = 1; i <= num_linhas; i++) {
// Inicializa a linha atual da DP com 0
memset(dp_max_canhoes[i & 1], 0, sizeof dp_max_canhoes[i & 1]);
// Itera sobre as configuracoes da linha atual
for (int j = 0; j < posicoes_validas.size(); j++) {
int config_atual = posicoes_validas[j];
// Itera sobre as configuracoes da linha anterior
for (int k = 0; k < posicoes_validas.size(); k++) {
int config_anterior = posicoes_validas[k];
// Itera sobre as configuracoes da linha duas posicoes atras
for (int u = 0; u < posicoes_validas.size(); u++) {
int config_duas_anterior = posicoes_validas[u];
// Condicoes de nao ataque entre 3 linhas consecutivas
// 1. Nenhuma sobreposicao de canhoes nas 3 linhas (config_atual & config_anterior & config_duas_anterior)
if ( (config_atual & config_anterior) || (config_atual & config_duas_anterior) || (config_anterior & config_duas_anterior) ) {
continue;
}
// 2. Nao colocar canhoes em montanhas na linha atual ou linha anterior
if ( (mapa_terreno[i] & config_atual) || (mapa_terreno[i - 1] & config_anterior) ) {
continue;
}
// 3. Nao colocar canhoes em montanhas na linha duas posicoes atras (somente se i >= 2)
if (i >= 2 && (mapa_terreno[i - 2] & config_duas_anterior) ) {
continue;
}
// Atualiza o valor maximo
// dp_max_canhoes[linha_atual][config_linha_atual][config_linha_anterior] =
// max( valor_atual, dp[linha_anterior][config_linha_duas_anterior][config_linha_anterior] + canhoes_na_linha_atual )
dp_max_canhoes[i & 1][j][k] = max(dp_max_canhoes[i & 1][j][k],
dp_max_canhoes[(i - 1) & 1][u][j] + contagem_canhoes[config_atual]);
}
}
}
}
int resultado_max = 0;
// O resultado final e o maximo valor em qualquer estado da ultima linha
for (int i = 0; i < posicoes_validas.size(); i++) {
for (int j = 0; j < posicoes_validas.size(); j++) {
resultado_max = max(resultado_max, dp_max_canhoes[num_linhas & 1][i][j]);
}
// Tambem considerar se a ultima linha foi 0 (nenhum canhao), se aplicavel
// resultado_max = max(resultado_max, dp_max_canhoes[num_linhas & 1][i][0]);
}
// A logica do problema implica que `dp_max_canhoes[n & 1][i][j]` ja considera todos os canhões até a linha `n`.
// Não é necessário somar canhões da linha n-1 e n-2, pois eles já foram somados em suas respectivas etapas.
// `contagem_canhoes[config_atual]` é o número de canhões apenas na `config_atual`.
// A soma `dp_max_canhoes[(i - 1) & 1][u][j] + contagem_canhoes[config_atual]` já constrói o total.
cout << resultado_max << endl;
return 0;
}
Exemplo 9: Angry Birds
Kiana joga um jogo onde ela lança pássaros de uma funda em (0,0) para atingir porcos verdes no primeiro quadrante. Os pássaros voam em trajetórias parabólicas y = ax^2 + bx com a < 0. Se um pássaro passa por um porco (xi,yi), o porco é eliminado. O objetivo é eliminar todos os n porcos com o mínimo de pássaros. Encontre o número mínimo de pássaros necessários.
Entrada: T (número de casos de teste). Para cada caso: N (número de porcos), M (tipo de comando - irrelevante para a lógica de DP principal). N linhas com (xi,yi) (coordenadas dos porcos).
Saída: Para cada caso, o número mínimo de pássaros.
Restrições: 1 ≤ N ≤ 18.
Este problema é um exemplo clássico de "Set Cover" (Cobertura de Conjuntos) resolvido com Bitmask DP. Como N é pequeno (≤18), podemos pré-calcular todas as trajetórias parabólicas possíveis que passam por pelo menos um ou dois porcos. Em seguida, usamos PD para encontrar o número mínimo de pássaros para cobrir todos os porcos.
parabola_cobre[i][j]: Uma máscara de bits representando todos os porcos atingidos por uma parábola que passa porporcos[i]eporcos[j]. Sei==j, é uma parábola que passa apenas porporcos[i](lançamento vertical ou para um único porco).dp[mascara_porcos_restantes]: O número mínimo de pássaros necessários para eliminar o conjunto de porcos representados pela máscara de bitsmascara_porcos_restantes.
As transições da DP são:
- Para cada estado
i(conjunto de porcos já eliminados), encontramos o porcoxque ainda não foi eliminado. - Para cada parábola possível que pode eliminar
x(passando porxe qualquer outro porcoj, ou apenasx), calculamos a próxima máscarai | parabola_cobre[x][j]. - Atualizamos
dp[i | parabola_cobre[x][j]] = min(dp[i | parabola_cobre[x][j]], dp[i] + 1).
Implementação em C++
#include <cstring>
#include <iostream>
#lt;algorithm>
#include <cmath> // Para fabs
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int MAX_PORCOS = 18;
const int MAX_MASK = 1 << MAX_PORCOS; // 2^18
const double EPS = 1e-8; // Tolerancia para comparacoes de ponto flutuante
int num_porcos, tipo_comando;
PDD coord_porcos[MAX_PORCOS]; // Coordenadas dos porcos
int parabola_cobre[MAX_PORCOS][MAX_PORCOS]; // parabola_cobre[i][j] = mascara de bits dos porcos atingidos pela parabola i-j
int dp_min_parabolas[MAX_MASK]; // dp_min_parabolas[mask] = min. aves para atingir porcos na mascara
// Funcao de comparacao para numeros de ponto flutuante
int comparar_double(double d1, double d2) {
if (fabs(d1 - d2) < EPS) return 0; // Sao considerados iguais
if (d1 < d2) return -1;
return 1;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> num_porcos >> tipo_comando;
for (int i = 0; i < num_porcos; i++) {
cin >> coord_porcos[i].x >> coord_porcos[i].y;
}
memset(parabola_cobre, 0, sizeof parabola_cobre);
// Pre-computa todas as parabolas e os porcos que elas atingem
for (int i = 0; i < num_porcos; i++) {
// Caso de parabola que passa por um unico porco (linha vertical, por exemplo)
parabola_cobre[i][i] = (1 << i);
for (int j = 0; j < num_porcos; j++) {
// Se i e j sao o mesmo porco, ja tratamos acima.
// Se as coordenadas X sao iguais, nao e uma parabola valida y=ax^2+bx (passa pela origem e x=0).
// Precisamos de x1 != x2 para definir a parabola de forma unica por 2 pontos.
if (comparar_double(coord_porcos[i].x, coord_porcos[j].x) == 0) continue;
double x1 = coord_porcos[i].x, y1 = coord_porcos[i].y;
double x2 = coord_porcos[j].x, y2 = coord_porcos[j].y;
// Calculo dos coeficientes a e b para y = ax^2 + bx
// Resolvendo o sistema:
// y1 = a*x1^2 + b*x1 => y1/x1 = a*x1 + b
// y2 = a*x2^2 + b*x2 => y2/x2 = a*x2 + b
// Subtraindo as equacoes: y1/x1 - y2/x2 = a*(x1 - x2)
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
// As parabolas devem ter a < 0 (curvatura para baixo)
if (comparar_double(a, 0) >= 0) continue;
int mascara_porcos_atingidos = 0;
// Para esta parabola, verifica quais porcos ela atinge
for (int k = 0; k < num_porcos; k++) {
double x_k = coord_porcos[k].x, y_k = coord_porcos[k].y;
if (comparar_double(a * x_k * x_k + b * x_k, y_k) == 0) {
mascara_porcos_atingidos |= (1 << k);
}
}
parabola_cobre[i][j] = mascara_porcos_atingidos;
}
}
memset(dp_min_parabolas, 0x3f, sizeof dp_min_parabolas); // Inicializa com infinito
dp_min_parabolas[0] = 0; // 0 aves para atingir 0 porcos
// DP para encontrar o minimo de parabolas
// Itera sobre todos os estados (mascaras de porcos ja atingidos)
for (int mascara_atual = 0; mascara_atual < (1 << num_porcos); mascara_atual++) {
if (dp_min_parabolas[mascara_atual] == 0x3f3f3f3f) continue; // Pula estados inatingiveis
int porco_nao_atingido_idx = -1;
// Encontra o primeiro porco nao atingido na mascara atual
for (int j = 0; j < num_porcos; j++) {
if (!(mascara_atual & (1 << j))) {
porco_nao_atingido_idx = j;
break;
}
}
if (porco_nao_atingido_idx == -1) continue; // Todos os porcos foram atingidos
// Tenta usar uma parabola para atingir o porco_nao_atingido_idx
// e possivelmente outros porcos.
// Para isso, a parabola deve passar pelo porco_nao_atingido_idx.
for (int j = 0; j < num_porcos; j++) {
// A parabola passa pelo porco_nao_atingido_idx e pelo porco j
int mascara_nova = mascara_atual | parabola_cobre[porco_nao_atingido_idx][j];
dp_min_parabolas[mascara_nova] = min(dp_min_parabolas[mascara_nova], dp_min_parabolas[mascara_atual] + 1);
}
}
cout << dp_min_parabolas[(1 << num_porcos) - 1] << endl; // Resultado para todos os porcos atingidos (mascara de todos os bits 1)
}
return 0;
}
Exemplo 10: Mapa do Tesouro
Um mapa do tesouro mostra N salas de tesouro subterrâneas e M estradas entre elas com seus comprimentos. Uma estrada do solo para uma sala de tesouro pode ser aberta gratuitamente por um patrocinador para uma sala escolhida por você. Em seguida, você deve abrir estradas entre as salas de tesouro já abertas. Cada nova estrada aberta custa: (comprimento da estrada) × (número de salas visitadas desde a sala inicial gratuita, incluindo a sala inicial e o ponto de partida da estrada). Encontre o custo mínimo total para visitar todas as salas de tesouro.
Entrada: N (salas), M (estradas). M linhas com A, B (salas conectadas) e V (comprimento da estrada).
Saída: O custo mínimo total.
Restrições: 1 ≤ N ≤ 12, 0 ≤ M ≤ 1000.
Este é um problema de Steiner Tree ou Minimum Spanning Tree modificado, mas com N pequeno, pode ser resolvido com Bitmask DP. A chave é o custo de abertura da estrada, que depende do número de salas já abertas. Os estados da DP são:
dp_custo_total[mascara_visitados][num_caminhos_abertos]: O custo mínimo para visitar o conjunto de salas representadas pormascara_visitados, tendo abertonum_caminhos_abertosestradas.
Além disso, precisamos pré-calcular o custo de conexão entre um conjunto de salas já visitadas e uma nova sala. A transição envolve escolher um subconjunto de salas já visitadas e uma nova sala para expandir o conjunto.
Implementação em C++
#include <cstdio>
#include <cstring>
#include <iostream>
#lt;algorithm>
using namespace std;
const int MAX_N_TESOUROS = 12;
const int MAX_MASK_TESOUROS = 1 << MAX_N_TESOUROS;
const int INF = 0x3f3f3f3f; // Valor para infinito
int num_tesouros, num_estradas;
int distancias[MAX_N_TESOUROS][MAX_N_TESOUROS]; // Matriz de adjacencia para distancias entre salas
int dp_custo_total[MAX_MASK_TESOUROS][MAX_N_TESOUROS];
// dp_custo_total[mascara_visitados][nivel_profundidade]:
// Custo minimo para visitar salas na mascara, sendo nivel_profundidade o numero de estradas abertas (exclui a gratuita)
int conectividade_com_mask[MAX_MASK_TESOUROS];
// conectividade_com_mask[mask]: mascara de bits de todos os nos que sao adjacentes a pelo menos um no em 'mask'
int main() {
scanf("%d%d", &num_tesouros, &num_estradas);
memset(distancias, 0x3f, sizeof distancias); // Inicializa distancias com infinito
for (int i = 0; i < num_tesouros; i++) {
distancias[i][i] = 0; // Distancia para si mesmo é 0
}
// Le as estradas e popula a matriz de distancias (grafo)
while (num_estradas--) {
int u, v, custo;
scanf("%d%d%d", &u, &v, &custo);
u--, v--; // Ajusta para 0-indexed
distancias[u][v] = distancias[v][u] = min(distancias[u][v], custo);
}
// Calcula conectividade_com_mask: para cada mascara, quais nos sao adjacentes a ela
for (int i = 1; i < (1 << num_tesouros); i++) {
for (int j = 0; j < num_tesouros; j++) {
if (i >> j & 1) { // Se a sala j está na mascara i
for (int k = 0; k < num_tesouros; k++) {
if (distancias[j][k] != INF) {
conectividade_com_mask[i] |= (1 << k); // Adiciona k aos nos conectados
}
}
}
}
}
memset(dp_custo_total, 0x3f, sizeof dp_custo_total); // Inicializa DP com infinito
// Caso base: uma sala é aberta gratuitamente
for (int i = 0; i < num_tesouros; i++) {
dp_custo_total[1 << i][0] = 0; // Custo 0 para visitar a primeira sala (0 estradas abertas)
}
// Iteracao principal da DP
// i: mascara de bits das salas ja visitadas
for (int i = 1; i < (1 << num_tesouros); i++) {
// j: mascara de bits de um subconjunto de salas ja visitadas (base para a proxima expansao)
// j é um subconjunto de i: j = (j-1) & i
for (int j = (i - 1); j; j = (j - 1) & i) {
// Se as salas em 'j' nao conectam todas as salas em 'i', continua
// (conectividade_com_mask[j] & i) == i significa que, dos nos em 'i', todos sao
// conectados por algum no em 'j'. Isso e um pouco confuso; eh mais como se 'j'
// fosse o conjunto de nos que ja foram visitados e 'i' e o conjunto de nos que
// queremos visitar, onde (i ^ j) sao os novos nos que serao visitados.
// A condicao (conectividade_com_mask[j] & i) == i verifica se todas as salas
// no conjunto 'i' sao adjacentes a pelo menos uma sala no subconjunto 'j'.
// Esta e a logica para uma "spanning forest" onde j sao os nós "root" do componente.
if ((conectividade_com_mask[j] & i) == i) {
int salas_a_conectar = i ^ j; // Salas em 'i' que nao estao em 'j' (novas salas)
int custo_conexao_novas_salas = 0;
// Calcula o custo para conectar as 'salas_a_conectar' ao conjunto 'j'
for (int k = 0; k < num_tesouros; k++) {
if (salas_a_conectar >> k & 1) { // Se k é uma das novas salas a conectar
int custo_min_para_k = INF;
for (int u = 0; u < num_tesouros; u++) {
if (j >> u & 1) { // Se u é uma sala ja visitada (no conjunto 'j')
custo_min_para_k = min(custo_min_para_k, distancias[k][u]);
}
}
custo_conexao_novas_salas += custo_min_para_k;
}
}
// Atualiza a DP
// k: numero de estradas ja abertas
for (int k = 1; k < num_tesouros; k++) {
dp_custo_total[i][k] = min(dp_custo_total[i][k], dp_custo_total[j][k - 1] + custo_conexao_novas_salas * k);
}
}
}
}
int custo_min_final = INF;
// O custo minimo e o menor valor para visitar todas as salas (mascara (1<<N)-1)
// com qualquer numero de estradas abertas
for (int i = 0; i < num_tesouros; i++) {
custo_min_final = min(custo_min_final, dp_custo_total[(1 << num_tesouros) - 1][i]);
}
printf("%d\n", custo_min_final);
return 0;
}