Introdução à DP de Intervalo Multidimensional

A Programação Dinâmica (DP) de intervalo é uma técnica poderosa para resolver problemas onde a solução de um intervalo maior depende de sub-intervalos menores. Em problemas mais complexos, o estado da DP não pode ser definido apenas pelos limites do intervalo $[i, j]$, exigindo dimensões adicionais para representar informações cruciais, como a posição atual do agente ou a última escolha efetuada.

Estudo de Caso 1: Otimização de Trajeto e Consumo (P1220)

Neste cenário, um técnico deve apagar luzes em uma rua. Cada luz possui uma posição e uma potência de consumo. O objetivo é minimizar a energia total desperdiçada enquanto o técnico se move para apagar todas as lâmpadas. O tempo gasto no deslocamento é proporcional à distância, e todas as lâmpadas acesas consomem energia continuamente.

Modelagem do Estado

Ao definir o estado como dp[i][j] representando o intervalo de luzes apagadas de $i$ a $j$, percebemos que o custo para alcançar o próximo estado depende de onde o técnico está: na extremidade esquerda ($i$) ou na direita ($j$). Portanto, adicionamos uma terceira dimensão:

• f[i][j][0]: Custo mínimo com o intervalo $[i, j]$ apagado, estando o técnico na posição $i$.
• f[i][j][1]: Custo mínimo com o intervalo $[i, j]$ apagado, estando o técnico na posição $j$.

Transição e Cálculo de Custo

Para calcular o desperdício durante o movimento, utilizamos somas de prefixo para obter rapidamente a potência total das luzes que ainda peramnecem acesas (aquelas fora do intervalo $[i, j]$).

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

using namespace std;

const int MAXN = 60;
long long f[MAXN][MAXN][2];
int coord[MAXN], prefix_potencia[MAXN];
int n, inicio;

long long calcular_custo(int origem, int destino, int i, int j) {
    long long tempo = abs(coord[origem] - coord[destino]);
    long long potencia_ativa = prefix_potencia[n] - (prefix_potencia[j] - prefix_potencia[i - 1]);
    return tempo * potencia_ativa;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> inicio;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> coord[i] >> p;
        prefix_potencia[i] = prefix_potencia[i - 1] + p;
    }

    memset(f, 0x3f, sizeof(f));
    f[inicio][inicio][0] = f[inicio][inicio][1] = 0;

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            
            // Chegando em i vindo de i+1 ou de j
            f[i][j][0] = min(f[i + 1][j][0] + calcular_custo(i + 1, i, i + 1, j),
                             f[i + 1][j][1] + calcular_custo(j, i, i + 1, j));
            
            // Chegando em j vindo de i ou de j-1
            f[i][j][1] = min(f[i][j - 1][0] + calcular_custo(i, j, i, j - 1),
                             f[i][j - 1][1] + calcular_custo(j - 1, j, i, j - 1));
        }
    }

    cout << min(f[1][n][0], f[1][n][1]) << endl;
    return 0;
}

Estudo de Caso 2: Formação de Fila com Restrições (P3205)

Considere a formação de um coro onde cada nova pessoa entra na fila pela esquerda ou pela direita. A regra é que a pessoa recém-chegada deve ser comparada com a pessoa que entrou imediatamente antes dela. Ela só pode entrar se for mais baixa (ou mais alta, dependendo da regra de modelagem) que a pessoa anterior.

Definição de Estado

Para contar as formas possíveis de compor o intervalo $[i, j]$, precisamos saber se a última pessoa adicionada está na posição $i$ ou $j$:

• dp[i][j][0]: Quantidade de formas de formar o intervalo $[i, j]$ onde a última pessoa entrou pela esquerda (posição $i$).
• dp[i][j][1]: Quantdiade de formas de formar o intervalo $[i, j]$ onde a última pessoa entrou pela direita (posição $j$).

Regras de Transição

Uma pessoa entra na posição $i$ se for mais baixa que a pessoa que entrou anteriormente (que poderia estar em $i+1$ ou em $j$). O mesmo raciocínio se aplica para a entrada na posição $j$.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 19650827;

int main() {
    int n;
    cin >> n;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(2, 0)));

    for (int i = 1; i <= n; i++) dp[i][i][0] = 1;

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;

            // Transições para dp[i][j][0] (último entrou em i)
            if (h[i] < h[i + 1]) dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][0]) % MOD;
            if (h[i] < h[j])     dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][1]) % MOD;

            // Transições para dp[i][j][1] (último entrou em j)
            if (h[j] > h[i])     dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][0]) % MOD;
            if (h[j] > h[j - 1]) dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][1]) % MOD;
        }
    }

    cout << (dp[1][n][0] + dp[1][n][1]) % MOD << endl;
    return 0;
}

Aálise Comparativa e Conclusão Técnica

Ambos os problemas compartilham a estrutura central da DP de intervalo. A necessidade de uma dimensão extra surge da perda de propriedade de Markov se considerarmos apenas o intervalo. Em problemas de trajeto (como o das lâmpadas), a posição atual altera o custo futuro. Em problemas de ordenação (como o coro), a última posição preenchida dita a validade da próxima inserção.

Ao implementar essas soluções, a atenção deve ser voltada para:

1. Inicialização: Definir corretamente o caso base (intervalo de tamanho 1).
2. Ordem de Processamento: Garantir que intervalos menores sejam calculados antes dos maiores (geralmente iterando sobre o comprimento do intervalo len).
3. Otimização de Espaço: Em alguns casos, é possível reduzir a dimensionalidade, embora em problemas de intervalo a clareza do estado $[i, j, k]$ seja preferível para evitar erros de lógica.