Programação Dinâmica com Mochila

Problemas de mochila envolvem a seleção de itens sob restrições de capacidade, visando maximizar valor ou minimizar custo. Existem variações clássicas com abordagens distintas:

• Mochila 0-1: cada item pode ser usado no máximo uma vez. A iteração é feita de forma decrescente na capacidade para evitar reutilização.
• Mochila Completa: cada item pode ser usado infinitamente. A iteração ocorre em ordem crescente.
• Mochila com Quantidades Limitadas: resolve-se por decomposição binária dos itens, transformando-a em uma sequência de decisões 0-1.
• Mochila por Grupos: em cada grupo, apenas um item pode ser escolhido. O laço interno percorre os itens do grupo atual.

Casos Especiais e Otimizações

Quando há dependência entre itens (ex: árvore de dependências), pode-se modelar como mochila em grupo após uma DFS. Em problemas de decisão (sim/não), o uso de bitset reduz significativamente o tempo de execução. Para instâncias com grandes valores de capacidade mas volumes pequenos, aplica-se uma combinação de greedy + DP precisa em resíduos.

Contagem de Soluções Ótimas

Além do valor ótimo, mantém-se um array auxiliar contando o número de formas de alcançar cada estado. Quando um novo valor estritamente melhor é encontrado, a contagem é reiniciada. Caso haja empate, as contagens são somadas.

Exemplos Práticos

• P1782: combina múltiplas e grupamento — resolve-se separadamente.
• P2014: dependência em árvore — usa-se DP com estado adicional indicando o nó raiz da subárvore.
• P2515: ciclo detectado via condensação de componentes fortemente conexos; reduz-se ao problema de escolha de disciplinas.
• P3188: integra programação dinâmica com bitmasking e múltiplas execuções.
• P4158: técnica incomum de transição com suporte de arrays secundários.
• P4322: explora a complexidade quadrática de mochila em árvores combinada com programação fracionária.
• P14508: identificação de equivalência entre estados permite compressão de estado.
• P4516: introduz dimensões extras para controlar se o vértice está selecionado ou coberto — padrão comum em problemas de cobertura.

Programação Dinâmica em Intervalos

Esta categoria lida com a divisão recursiva de intervalos contíguos. Define-se f[l][r] como o valor máximo obtido ao fundir elementos do índice l ao r. A transição típica é:

f[l][r] = max{ f[l][k] + f[k+1][r] + custo }

Onde k varia entre l e r-1, representando o ponto de cisão.

Estratégias Comuns

• Analisar qual operação ocorre por último (ou primeira).
• Fixar o último elemento incluído para facilitar contagem.

Tratamento de Estruturas Circulares

Transforma-se o anel em uma cadeia duplicada de tamanho 2n, aplicando a DP sobre todos os segmentos de comprimento n e tomando o melhor resultado.

Aplicações

• P2470: definição direta de estado em intervalo.

• P7414: aplicação direta com pré-requisito teórico.

• P3147: possível aceleração com técnica de exponenciação rápida em etapas de fusão.

• Modelo "apagar postes de luz":

• P11432: versão reversa do problema clássico.

• P2466: necessita pré-processamento mais elaborado.

• P4870: função de custo baseada em janela temporal.

• P4766: analisa última ação realizada; [l,r] representa regiões completamente cobertas.

• P9493: preenchimento simétrico a partir das bordas torna natural a formulação intervalar.

• P13586: correspondência de pilha leva a estrutura similar à casamento de parênteses — resolvido com DP intervalar.

• P8227: modelo recursivo com subdivisão sucessiva.

DP em Grafos Acíclicos Direcionados (DAG)

DAGs permitem ordenação topológica, o que facilita a computação sequencial de estados. Relações binárias entre elementos frequentemente geram grafos desse tipo.

Otimização de Conectividade

Para calcular alcance em DAGs (ex: quais vértices atingem outros), utiliza-se bitset para compactar informações de vizinhança. Isso reduz a complexidade para O(n² / w), onde w é a largura da palavra (geralmente 32 ou 64).

Exercícios Representativos

• P4099: conta o número de ordenações topológicas possíveis — desafio avançado.

Programação Dinâmica em Árvores

Explora a estrutura hierárquica e recursiva de árvores. Normalmente implementada via DFS, com estados associados a subárvores.

Observações Importantes

• Definir claramente o significado do estado antes de codificar evita erros durante depuração.
• Em grafos com ciclos (ex: pseudoflorestas), técnicas comuns incluem:
  • Detecção de ciclo por eliminação iterativa (topológico).
  • Quebra do ciclo e execução múltipla de DP em árvore.
  • Uso de fila duplamente terminada para cálculo de diâmetro em ciclos.

Exemplos Selecionados

• P1269: combina greedy simples com DP.
• P1270: extensão direta de mochila com dependência em árvore.
• P1453, P1543: generalização para grafos com ciclo único (base-ciclo). Abordagens incluem remoção do ciclo e repetição do processo.
• P2607: verificação de estrutura base-ciclo com base em graus de entrada/saída.
• P3177: demonstra por que a complexidade de mochila em árvores é O(n²).
• P3574, P5521: modelos clássicos com ordenação ótima baseada em diferença g[i] - f[i], provada por troca de vizinhos.
• P6554: mudança de raiz (rerooting) com manipulação cuidadosa de estados.
• P6594: integra busca binária com propriedades de amplitude (range mínimo-máximo).
• P7925: recursão com otimização usando conjuntos disjuntos (DSU on trees).
• P8089: contagem básica em árvore.
• P9745: projeto de estado não trivial, exigindo análise bit a bit para contabilizar contribuições.
• P11766: explora propriedade de que caminhos mais longos passam pelo centro do diâmetro.
• P11850: diâmetro em base-ciclo usando deque.
• P3523: combina busca binária com arrays auxiliares.
• P6419: simplificado ao considerar contribuição de arestas dividindo componentes.

Programação Dinâmica com Compactação de Estados (Bitmask)

Representa conjuntos ou configurações usando inteiros, aproveitando operações bitwise para eficiência. Comum em problemas com estados binários independentes (ativo/inativo, visitado/não visitado).

Técnicas Úteis

Enumeração de Subconjuntos:

for (int sub = mask; sub; sub = (sub - 1) & mask)

Permite percorrer todos os subconjuntos não vazios de mask em tempo O(3ⁿ).

Soma de Prefixos em Dimensões Binárias (SOS DP):

for (int j = 0; j < n; j++)
  for (int i = 0; i < (1 << n); i++)
    if (!(i >> j & 1))
      dp[i] += dp[i | (1 << j)];

Calcula a soma sobre todos os superconjuntos em tempo O(n·2ⁿ).

Composições Avançadas

Combinações com matriz de transição e exponenciação rápida surgem em problemas com evolução temporal de estados discretos.

Problemas Ilustrativos

• P2704, P2831, P3694: exemplos introdutórios.
• P7296: transição especial com condição não usual.
• P1357: uso de exponenciação rápida de matrizes.
• P2150, P3226: otimizações na enumeração de estados.
• P2157: integração com DP linear parcial.
• P3959: exploração completa de submasks.
• P5933: aplicação em probabilidade de conectividade em subgrafos — caso avançado de contagem com estados compactados.