Neste artigo, exploraremos diversas abordagens algorítmicas, com foco em Programação Dinâmica (PD) de intervalo e estruturas de dados de otimização, aplicadas a problemas clássicos de fusão e corte. A PD de intervalo é uma técnica poderosa para resolver problemas onde a solução ótima de um problema maior pode ser construída a partir de soluções ótimas de subproblemas menores, geralmente definidos por subintervalos.
UVA 10954: Soma de Custos Mínimos
Descrição do Problema:
Dado um conjunto de N números inteiros, o objetivo é combiná-los em um único número. Cada operação consiste em escolher dois números, somá-los e adicionar o resultado de volta ao conjunto. O custo de uma operação é a soma dos dois números escolhidos. O processo continua até que apenas um número permaneça. O problema pede para encontrar o custo total mínimo para realizar todas as fusões.
Estratégia:
Este problema pode ser resolvido de forma eficiente usando uma abordagem gulosa com uma fila de prioridade mínima. A intuição é que, para minimizar a soma total, devemos sempre fundir os dois menores números disponíveis a cada passo. Isso é análogo ao algoritmo de Huffman para construção de árvores ótimas.
Implementação em C++:
#include <iostream>
#include <vector>
#include <queue>
#include <functional> // Para std::greater
void processa_casos(int n_elementos) {
std::priority_queue<long long, std::vector<long long>, std::greater<long long>> fila_minima;
for (int i = 0; i < n_elementos; ++i) {
long long valor_atual;
std::cin >> valor_atual;
fila_minima.push(valor_atual);
}
long long custo_total = 0;
while (fila_minima.size() > 1) {
long long primeiro_elemento = fila_minima.top();
fila_minima.pop();
long long segundo_elemento = fila_minima.top();
fila_minima.pop();
long long soma_temp = primeiro_elemento + segundo_elemento;
fila_minima.push(soma_temp);
custo_total += soma_temp;
}
std::cout << custo_total << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int n_elementos_entrada;
while (std::cin >> n_elementos_entrada && n_elementos_entrada != 0) {
processa_casos(n_elementos_entrada);
}
return 0;
}
UVA 10003: Cortando Varetas
Descrição do Problema:
Uma vareta de madeira de um certo comprimento precisa ser cortada em vários pontos. Os pontos de corte são especificados por suas distâncias a partir de uma das extremidades da vareta. O custo de um corte é igual ao comprimento da vareta que está sendo cortada naquele momento. O objetivo é determinar a sequência de cortes que minimiza o custo total.
Estratégia Inicial e Refinamento:
A princípio, pode-se tentar associar este problema à ideia de fusão de pilhas, mas a natureza dos custos e das operações é fundamentalmente diferente. Para o problema de corte, os cortes devem ser feitos em segmentos contíguos. Isso sugere uma abordagem de Programação Dinâmica de intervalo.
Seja a vareta de comprimento L e os pontos de corte c1, c2, ..., cn. Podemos conceptualizar o problema como a fusão de segmentos. Primeiro, criamos uma lista de todos os pontos relevantes: 0 (início), c1, ..., cn e L (fim). Em seguida, calculamos os comprimentos dos segmentos entre esses pontos. Por exemplo, se os pontos forem p0, p1, ..., pm, onde p0=0 e pm=L, os segmentos iniciais teriam comprimentos p1-p0, p2-p1, ..., pm-p(m-1).
O estado da PD pode ser definido como dp[i][j], representando o custo mínimo para cortar a sub-vareta que vai do i-ésimo ponto ao j-ésimo ponto. A transição envolve testar todos os pontos de corte intermediários k entre i e j:
dp[i][j] = min(dp[i][k] + dp[k][j] + (p_j - p_i))
O termo (p_j - p_i) representa o comprimento da vareta atual, que é o custo de fazer o corte em k. Note que aqui p_i e p_j são os valores dos pontos de corte *originais* (incluindo 0 e L), e não os índices dos segmentos após a primeira transformação.
Para N ≤ 50, uma complexidade de O(N^3) é aceitável.
Luogu P1775: Fusão de Pedras (Versão Linear)
Descrição do Problema:
Dadas N pilhas de pedras em uma linha, o objetivo é fundi-las em uma única pilha. A cada passo, duas pilhas adjacentes são selecionadas e fundidas. O custo de uma fusão é a soma das massas das duas pilhas. O problema pede o custo total mínimo para fundir todas as pilhas.
Estratégia:
Este é um problema clássico de Programação Dinâmica de intervalo. Definimos dp[i][j] como o custo mínimo para fundir as pilhas do índice i ao índice j. Para calcular dp[i][j], consideramos todos os possíveis pontos de divisão k entre i e j-1. O custo seria a soma do custo de fundir [i, k], o custo de fundir [k+1, j], mais o custo da última fusão que une essas duas grandes pilhas, que é a soma total das pilhas de i a j.
Para otimizar o cálculo da soma das pilhas, utilizamos somas de prefixo. somas_prefixo[x] armazena a soma das pilhas de 1 a x. Assim, a soma das pilhas de i a j é somas_prefixo[j] - somas_prefixo[i-1].
A iteração da PD deve ser por comprimento do entervalo (comprimento\_intervalo), de 2 até N, garantindo que os subproblemas menores sejam resolvidos antes dos maiores.
Implementação em C++:
#include <iostream>
#include <vector>
#include <numeric> // Para std::accumulate
#include <algorithm> // Para std::min
#include <limits> // Para std::numeric_limits
void resolver_problema_linear() {
int n_pilhas;
std::cin >> n_pilhas;
std::vector<long long> massas_pilhas(n_pilhas + 1);
std::vector<long long> somas_prefixo(n_pilhas + 1, 0);
for (int i = 1; i <= n_pilhas; ++i) {
std::cin >> massas_pilhas[i];
somas_prefixo[i] = somas_prefixo[i-1] + massas_pilhas[i];
}
std::vector<std::vector<long long>> custo_minimo_dp(n_pilhas + 1, std::vector<long long>(n_pilhas + 1, std::numeric_limits<long long>::max()));
// Inicializa dp[i][i] como 0, pois fundir uma única pilha não tem custo
for (int i = 1; i <= n_pilhas; ++i) {
custo_minimo_dp[i][i] = 0;
}
// Iteração por comprimento do intervalo
for (int comprimento_intervalo = 2; comprimento_intervalo <= n_pilhas; ++comprimento_intervalo) {
// Iteração por início do intervalo
for (int inicio = 1; inicio <= n_pilhas - comprimento_intervalo + 1; ++inicio) {
int fim = inicio + comprimento_intervalo - 1;
long long custo_fusao_total_intervalo = somas_prefixo[fim] - somas_prefixo[inicio - 1];
// Iteração por ponto de divisão (k)
for (int ponto_divisao = inicio; ponto_divisao < fim; ++ponto_divisao) {
custo_minimo_dp[inicio][fim] = std::min(
custo_minimo_dp[inicio][fim],
custo_minimo_dp[inicio][ponto_divisao] + custo_minimo_dp[ponto_divisao + 1][fim] + custo_fusao_total_intervalo
);
}
}
}
std::cout << custo_minimo_dp[1][n_pilhas] << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
resolver_problema_linear();
return 0;
}
P1880 \[NOI1995\]: Fusão de Pedras (Versão Circular)
Descrição do Problema:
Similar ao problema anterior, mas as pilhas de pedras estão dispostas em um círculo, o que significa que a primeira e a última pilha são adjacentes. O objetivo é encontrar tanto o custo total mínimo quanto o custo total máximo para fundir todas as pilhas.
Estratégia:
Para lidar com a natureza circular, uma técnica comum é "dobrar" o arranjo linear. Se temos N pilhas p1, p2, ..., pN, criamos um novo arranjo p1, p2, ..., pN, p1, p2, ..., pN (total de 2*N pilhas). Agora, qualquer sequência de N pilhas adjacentes no círculo pode ser representada como um intervalo de comprimento N no arranjo dobrado.
A Programação Dinâmica de intervalo é aplicada da mesma forma, mas agora precisaremos de duas tabelas DP: uma para custos mínimos (custos_minimos_dp) e outra para custos máximos (custos_maximos_dp). A inicialização para custos\_maximos\_dp deve usar um valor negativo muito pequeno.
Após preencher as tabelas DP para o arranjo dobrado (com 2*N elementos), a resposta final será o mínimo/máximo de dp[i][i + N - 1] para todos os i de 1 a N (ou N+1, dependendo da indexação).
Implementação em C++:
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
void resolver_problema_circular() {
int n_pilhas;
std::cin >> n_pilhas;
std::vector<long long> massas_pilhas_duplicadas(2 * n_pilhas + 1);
std::vector<long long> somas_acumuladas(2 * n_pilhas + 1, 0);
for (int i = 1; i <= n_pilhas; ++i) {
std::cin >> massas_pilhas_duplicadas[i];
massas_pilhas_duplicadas[i + n_pilhas] = massas_pilhas_duplicadas[i]; // Duplica para formar o círculo
}
// Calcula somas de prefixo para o arranjo duplicado
for (int i = 1; i <= 2 * n_pilhas; ++i) {
somas_acumuladas[i] = somas_acumuladas[i-1] + massas_pilhas_duplicadas[i];
}
std::vector<std::vector<long long>> custos_minimos_dp(2 * n_pilhas + 1, std::vector<long long>(2 * n_pilhas + 1));
std::vector<std::vector<long long>> custos_maximos_dp(2 * n_pilhas + 1, std::vector<long long>(2 * n_pilhas + 1));
// Inicializa tabelas DP
for (int i = 1; i <= 2 * n_pilhas; ++i) {
for (int j = 1; j <= 2 * n_pilhas; ++j) {
if (i == j) {
custos_minimos_dp[i][j] = 0;
custos_maximos_dp[i][j] = 0;
} else {
custos_minimos_dp[i][j] = std::numeric_limits<long long>::max();
custos_maximos_dp[i][j] = std::numeric_limits<long long>::min();
}
}
}
// Iteração por comprimento do intervalo
for (int comprimento_atual = 2; comprimento_atual <= n_pilhas; ++comprimento_atual) {
// Iteração por início do intervalo no arranjo duplicado
for (int inicio = 1; inicio <= 2 * n_pilhas - comprimento_atual + 1; ++inicio) {
int fim = inicio + comprimento_atual - 1;
long long custo_base_intervalo = somas_acumuladas[fim] - somas_acumuladas[inicio - 1];
// Iteração por ponto de divisão (ponto_intermedio)
for (int ponto_intermedio = inicio; ponto_intermedio < fim; ++ponto_intermedio) {
// Cálculo do custo mínimo
custos_minimos_dp[inicio][fim] = std::min(
custos_minimos_dp[inicio][fim],
custos_minimos_dp[inicio][ponto_intermedio] + custos_minimos_dp[ponto_intermedio + 1][fim] + custo_base_intervalo
);
// Cálculo do custo máximo
custos_maximos_dp[inicio][fim] = std::max(
custos_maximos_dp[inicio][fim],
custos_maximos_dp[inicio][ponto_intermedio] + custos_maximos_dp[ponto_intermedio + 1][fim] + custo_base_intervalo
);
}
}
}
long long resultado_minimo = std::numeric_limits<long long>::max();
long long resultado_maximo = std::numeric_limits<long long>::min();
// Encontra o mínimo/máximo entre todos os intervalos de comprimento N
for (int i = 1; i <= n_pilhas; ++i) { // O loop pode ir até n_pilhas para cobrir todas as rotações
resultado_minimo = std::min(resultado_minimo, custos_minimos_dp[i][i + n_pilhas - 1]);
resultado_maximo = std::max(resultado_maximo, custos_maximos_dp[i][i + n_pilhas - 1]);
}
std::cout << resultado_minimo << std::endl;
std::cout << resultado_maximo << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
resolver_problema_circular();
return 0;
}
UVA 10003: Solução Final para Cortando Varetas
Revisitando o problema "Cortando Varetas" (UVA 10003), sua restrição de N ≤ 50 (número de cortes) confirma que a solução de Programação Dinâmica de entervalo com complexidade O(N^3) é perfeitamente viável.
O truque fundamental é pré-processar os pontos de corte. A vareta original vai de 0 a L. Os pontos de corte dados são c1, c2, ..., cn. Podemos adicionar 0 e L à lista de pontos de corte, ordená-los e então calcular os comprimentos dos segmentos que eles definem. Por exemplo, se os pontos ordenados forem p0, p1, ..., pm, onde p0=0 e pm=L, os "itens" a serem "fundidos" (ou cujos cortes são otimizados) são esses segmentos de comprimento p_{i+1} - p_i. O custo de cortar um segmanto de p_i a p_j é p_j - p_i.
Implementação em C++:
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
void calcular_cortes_minimos(int comprimento_total_vareta) {
int num_cortes;
std::cin >> num_cortes;
std::vector<int> pontos_de_corte_input(num_cortes);
for (int i = 0; i < num_cortes; ++i) {
std::cin >> pontos_de_corte_input[i];
}
// Adiciona as extremidades da vareta aos pontos de corte e ordena
std::vector<int> pontos_ordenados;
pontos_ordenados.push_back(0); // Início da vareta
for (int ponto : pontos_de_corte_input) {
pontos_ordenados.push_back(ponto);
}
pontos_ordenados.push_back(comprimento_total_vareta); // Fim da vareta
std::sort(pontos_ordenados.begin(), pontos_ordenados.end());
int n_segmentos_logicos = pontos_ordenados.size(); // Inclui 0 e L
// dp[i][j] representa o custo mínimo para cortar a vareta entre pontos_ordenados[i] e pontos_ordenados[j]
std::vector<std::vector<long long>> custo_corte_dp(n_segmentos_logicos, std::vector<long long>(n_segmentos_logicos));
// Inicializa a tabela DP
for (int i = 0; i < n_segmentos_logicos; ++i) {
for (int j = 0; j < n_segmentos_logicos; ++j) {
if (i == j || i + 1 == j) { // Um único ponto ou um segmento já formado não tem custo de corte adicional
custo_corte_dp[i][j] = 0;
} else {
custo_corte_dp[i][j] = std::numeric_limits<long long>::max();
}
}
}
// Iteração por comprimento do intervalo
for (int comprimento_atual = 2; comprimento_atual < n_segmentos_logicos; ++comprimento_atual) {
// Iteração por início do intervalo
for (int inicio_idx = 0; inicio_idx < n_segmentos_logicos - comprimento_atual; ++inicio_idx) {
int fim_idx = inicio_idx + comprimento_atual;
long long custo_segmento_atual = pontos_ordenados[fim_idx] - pontos_ordenados[inicio_idx];
// Iteração por ponto de divisão (ponto_intermedio_idx)
for (int ponto_intermedio_idx = inicio_idx + 1; ponto_intermedio_idx < fim_idx; ++ponto_intermedio_idx) {
custo_corte_dp[inicio_idx][fim_idx] = std::min(
custo_corte_dp[inicio_idx][fim_idx],
custo_corte_dp[inicio_idx][ponto_intermedio_idx] + custo_corte_dp[ponto_intermedio_idx][fim_idx] + custo_segmento_atual
);
}
}
}
std::cout << "The minimum cutting is " << custo_corte_dp[0][n_segmentos_logicos - 1] << ".\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int comprimento;
while (std::cin >> comprimento && comprimento != 0) {
calcular_cortes_minimos(comprimento);
}
return 0;
}