Otimização com Filas Monótonas

A otimização utilizando estruturas de fila monótona é frequentemente aplicada quando o estado atual depende da melhor escolha dentro de uma janela deslizante restrita pelo tempo ou capacidade.

Considere a relação de recorrência onde buscamos o máximo em um intervalo:

Implementação Baseada em Array

Em vez de usar bibliotecas padrão, aqui apresentamos uma impleemntação manual eficiente focada no gerenciamento de ponteiros.

// Vetores para armazenar os índices válidos
std::vector<int> fila_indices;
int inicio_fila = 0;

for (int idx = 1; idx <= n; ++idx) {
    // Remove elementos inválidos fora da janela de alcance
    while (!fila_indices.empty() && fila_indices[inicio_fila] < idx - M) {
        inicio_fila++;
    }
    
    // Se houver candidatos, calcula o valor ótimo
    if (!fila_indices.empty()) {
        int candidato = fila_indices[inicio_fila];
        custo_atual[candidato]; // Uso simplificado do valor DP anterior
    }
    
    // Mantém a propriedade de ordenação (decrescente para máximo)
    while (!fila_indices.empty() && valor_em_fila(fila_indices.back()) <= valor_candidato(idx)) {
        fila_indices.pop_back();
    }
    
    fila_indices.push_back(idx);
}

Múltiplos Pacotes e Agrupamento por Resto

No problema clássico da mochila múltipla, podemos reduzir a complexidade dividindo os itens ponderados segundo seu resto quando dividido pelo peso específico. Para cada classe de restos, aplicamos a lógica de translação linear sobre o índice de capacidade, permitindo o uso da fila monótona descrita anteriormente para processar grupos independentes em tempo quase linear.

Desigualdade Quadrilátera e Decisão Monotônica

Quando a função de custo satisfaz a propriedade de submodularidade (conhecida como desigualdade quadrilátera), o ponto de decisão ótimo tende a mover-se em uma direção específica conforme o índice de destino aumenta. Isso define a chamada Monotonicidade de Decisão.

Rotina de Divisão e Conquista

A função recursiva abaixo limita o intervalo de candidatos (optMin a optMax) baseando-se nos resultados parciais já calculados.

void processar_recursivo(int l_esq, int l_dir, int opt_lim_inf, int opt_lim_sup, int etapa) {
    if (l_esq > l_dir || opt_lim_inf > opt_lim_sup) return;
    
    int meio_pos = (l_esq + l_dir) >> 1;
    int melhor_k = -1;
    double melhor_val = INFINITO;
    
    // Busca exaustiva dentro da faixa permitida pela monotonicidade
    for (int k = opt_lim_inf; k <= std::min(opt_lim_sup, meio_pos); ++k) {
        double val = custo_transicao(k, meio_pos);
        if (val < melhor_val) {
            melhor_val = val;
            melhor_k = k;
        }
    }
    
    tabela_dp[etapa][meio_pos] = melhor_val;
    
    // Recursão: esquerda vê decisões anteriores, direita vê futuras
    processar_recursivo(l_esq, meio_pos - 1, opt_lim_inf, melhor_k, etapa);
    processar_recursivo(meio_pos + 1, l_dir, melhor_k, opt_lim_sup, etapa);
}

Otimização via Árvore de Segmentos

Certais problemas exigem consultas de mínimo/máximo sobre intervalos dinâmicos durante a construção da tabela de DP. Uma árvore de segmentos com propagação preguiçosa (lazy propagation) permite realizar atualizações e consultas em logaritmo de tempo.

Exemplo clássico: particionamento de sequência minimizando soma de máximos locais sob restrições de soma de partes.

Estrutura de Dados Adaptada

Nós armazenamos não apenas o valor mínimo acumulado, mas também o impacto potencial das mudanças nas alturas máximas do segmento atual.

struct NoArvore {
    int min_acumulado;
    int ajuste_maximo;
    int propagador;
};

NoArvore arvore[MAX_N << 2];

// Propaga alterações pendentes para filhos
void aplicar_lazy(int u) {
    if (arvore[u].propagador != 0) {
        int filho_esq = u << 1;
        int filho_dir = (u << 1) | 1;
        
        arvore[filho_esq].ajuste_maximo += arvore[u].propagador;
        arvore[filho_esq].min_acumulado += arvore[u].propagador;
        arvore[filho_esq].propagador += arvore[u].propagador;
        
        arvore[filho_dir].ajuste_maximo += arvore[u].propagador;
        arvore[filho_dir].min_acumulado += arvore[u].propagador;
        arvore[filho_dir].propagador += arvore[u].propagador;
        
        arvore[u].propagador = 0;
    }
}

// Atualização pontual do estado DP
void inserir_estado(int u, int L, int R, int pos, int valor) {
    if (L == R) {
        arvore[u].ajuste_maximo = valor;
        arvore[u].min_acumulado = valor;
        return;
    }
    aplicar_lazy(u);
    int mid = (L + R) >> 1;
    if (pos <= mid) inserir_estado(u << 1, L, mid, pos, valor);
    else inserir_estado((u << 1) | 1, mid + 1, R, pos, valor);
    arvore[u].min_acumulado = std::min(arvore[u << 1].min_acumulado, 
                                       arvore[(u << 1) | 1].min_acumulado);
}

// Consulta no intervalo relevante
int obter_minimo(int u, int L, int R, int alvo_i, int alvo_f) {
    if (alvo_i > R || alvo_f < L) return INF;
    if (alvo_i <= L && R <= alvo_f) return arvore[u].min_acumulado;
    
    aplicar_lazy(u);
    int mid = (L + R) >> 1;
    return std::min(obter_minimo(u << 1, L, mid, alvo_i, alvo_f),
                    obter_minimo((u << 1) | 1, mid + 1, R, alvo_i, alvo_f));
}

Otimização Geométrica (Slope / Convex Hull)

Para equações do tipo linear $y = mx + c$, onde queremos maximizar ou minimizar $c$ dado $m$, podemos interpretar os estados anteriores como pontos num plano cartesiano $(x_j, y_j)$ e o coeficiente angular como inclinação fixa para o índice atual. Manter o envolvente convexo inferior ou superior desses pontos permite selecionar o melhor predecessor em $O(\log N)$ ou $O(1)$.

Lógica de Interseção Linear

A verificação entre três pontos consecutivos determina se um ponto intermediário ainda é útil.

// Função auxiliar para calcular inclinação entre dois estados
double inclinar(int p1, int p2) {
    long long y1 = Y_VAL(p1), y2 = Y_VAL(p2);
    long long x1 = X_VAL(p1), x2 = X_VAL(p2);
    if (x1 == x2) return (y1 >= y2) ? INF : -INF;
    return (double)(y1 - y2) / (double)(x1 - x2);
}

// Loop principal de otimização
void executar_passada(int fase_atual) {
    std::vector<int> pilha_idx;
    pilha_idx.push_back(0);
    
    for (int i = 1; i <= n; ++i) {
        int K = coeficiente_angulo(i);
        
        // Elimina vértices superiores desnecessários para maximização
        while (pilha_idx.size() >= 2) {
            if (inclinar(pilha_idx[0], pilha_idx[1]) <= K) {
                pilha_idx.erase(pilha_idx.begin());
            } else {
                break;
            }
        }
        
        int melhor_antecessor = pilha_idx.front();
        dp[i][fase_atual] = calcular_custo(melhor_antecessor, i);
        
        // Insere novo ponto mantendo convexasidade
        while (pilha_idx.size() >= 2) {
            if (inclinar(pilha_idx[pilha_idx.size()-2], pilha_idx.back()) >= 
                inclinar(pilha_idx.back(), i)) {
                pilha_idx.pop_back();
            } else {
                break;
            }
        }
        pilha_idx.push_back(i);
    }
}</int>

Heurísticas Gerais para Otimização de Estados

• Simplifique a fórmula matemática antes de tentar codificar; muitas vezes termos comuns podem ser fatorados.
• Analisie se a ordem de iteração pode ser alterada para permitir acesso sequencial aos dados ou cache.
• Identifique padrões repetitivos na matriz de custos e agrupe-os para computação em lote.
• Utilize estruturas de dados avançadas apenas quando a dependência entre estados envolver intervalos arbitrários ou condições complexas.