Este artículo aborda la resolución de un problema clásico de programación dinámica (DP) que involucra la selección de elementos con una restricción sobre secuencias consecutivas, utilizando una cola monótona para optimizar el cálculo de la transición.
Enunciado del Problema:
Se nos proporciona una secuencia de \\(N\\) números enteros positivos: \\(a\_1, a\_2, \dots, a\_N\\). El objetivo es seleccionar un subconjunto de estos números de tal manera que la suma de los números seleccionados sea máxima. Sin embargo, existe una restricción importante: no se pueden seleccionar más de \\(K\\) números consecutivos. Es decir, si se selecciona un bloque de números \\(a\_i, a\_{i+1}, \dots, a\_j\\), entonces \\(j - i + 1\\) debe ser menor o igual a \\(K\\).
Análisis y Solución mediante Programación Dinámica
Consideremos primero una versión más simple del problema, donde la restricción es que no se pueden seleccionar números adyacentes (es decir, \\(K=1\\), pero formulado como "no adyacentes"). Para este caso, una solución de DP es directa:
- \\(dp\_sin[i]\\): La suma máxima hasta el índice \\(i\\) si el número \\(a\_i\\) NO es seleccionado.
- \\(dp\_con[i]\\): La suma máxima hasta el índice \\(i\\) si el número \\(a\_i\\) SÍ es seleccionado.
Las transiciones serían:
- \\(dp\_sin[i] = \max(dp\_sin[i-1], dp\_con[i-1])\\) (Si no elegimos \\(a\_i\\), podemos haber elegido o no \\(a\_{i-1}\\)).
- \\(dp\_con[i] = dp\_sin[i-1] + a\_i\\) (Si elegimos \\(a\_i\\), entonces \\(a\_{i-1}\\) no pudo haber sido elegido).
El caso base \\(dp\_sin[0] = 0, dp\_con[0] = 0\\) (o manejar los índices apropiadamente). El resultado final sería \\(\max(dp\_sin[N], dp\_con[N])\\).
Implementación de la versión simple:
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_elementos;
std::cin >> num_elementos;
std::vector<long long> valores_input(num_elementos + 1);
for (int i = 1; i <= num_elementos; ++i) {
std::cin >> valores_input[i];
}
std::vector<long long> dp_no_tomar(num_elementos + 1, 0); // Max suma si a[i] NO es tomado
std::vector<long long> dp_tomar(num_elementos + 1, 0); // Max suma si a[i] SÍ es tomado
for (int i = 1; i <= num_elementos; ++i) {
dp_no_tomar[i] = std::max(dp_no_tomar[i - 1], dp_tomar[i - 1]);
dp_tomar[i] = dp_no_tomar[i - 1] + valores_input[i];
}
std::cout << std::max(dp_no_tomar[num_elementos], dp_tomar[num_elementos]) << std::endl;
return 0;
}
El Problema Original con Restricción \\(K\\)
La restricción de "no más de \\(K\\) números consecutivos" complica la transición de DP. Si elegimos \\(a\_i\\), ya no es suficiente solo mirar \\(a\_{i-1}\\). Podríamos haber elegido \\(a\_{i-1}, \dots, a\_{i-k+1}\\) antes de \\(a\_i\\), o cualquier secuencia de longitud menor. Esto significa que si \\(a\_i\\) es elegido, la última vez que un número NO fue elegido debe haber sido en algún índice \\(j\\) tal que el segmento \\(a\_{j+1}, \dots, a\_i\\) tenga una longitud máxima de \\(K\\). Es decir, \\(i - (j+1) + 1 \le K \implies i - j \le K \implies j \ge i - K\\).
Definamos los estados de DP de manera similar:
- \\(dp\_excluye[i]\\): La suma máxima hasta el índice \\(i\\) si \\(a\_i\\) NO es seleccionado.
- \\(dp\_incluye[i]\\): La suma máxima hasta el índice \\(i\\) si \\(a\_i\\) SÍ es seleccionado.
La transición para \\(dp\_excluye[i]\\) sigue siendo la misma:
\\(dp\_excluye[i] = \max(dp\_excluye[i-1], dp\_incluye[i-1])\\)
Para \\(dp\_incluye[i]\\), si seleccionamos \\(a\_i\\), entonces debemos haber llegado a este punto seleccionando un bloque de números que termina en \\(a\_i\\). Este bloque debe haber comenzado en \\(a\_{j+1}\\), donde \\(a\_j\\) fue el último número no seleccionado antes de este bloque. Por lo tanto, necesitamos encontrar el mejor \\(j\\) tal que \\(j \in [\max(0, i-K), i-1]\\). La suma en este caso sería la suma máxima hasta \\(j\\) sin incluir \\(a\_j\\), más la suma de los números desde \\(a\_{j+1}\\) hasta \\(a\_i\\).
Es decir, \\(dp\_incluye[i] = \max_{j=\max(0, i-K)}^{i-1} (dp\_excluye[j] + \sum_{l=j+1}^{i} a_l)\\)
Para calcular eficientemente \\(\sum_{l=j+1}^{i} a_l\\), podemos usar sumas de prefijo. Sea \\(S[x] = \sum_{l=1}^{x} a_l\\). Entonces \\(\sum_{l=j+1}^{i} a_l = S[i] - S[j]\\).
Sustituyendo esto en la ecuación de \\(dp\_incluye[i]\\):
\\(dp\_incluye[i] = \max_{j=\max(0, i-K)}^{i-1} (dp\_excluye[j] + S[i] - S[j])\\)
\\(dp\_incluye[i] = S[i] + \max_{j=\max(0, i-K)}^{i-1} (dp\_excluye[j] - S[j])\\)
El término \\(\max_{j=\max(0, i-K)}^{i-1} (dp\_excluye[j] - S[j])\\) es un máximo sobre una ventana deslizante. Esto se puede calcular eficientemente utilizando una cola monótona (también conocida como deque).
Cola Monótona para Máximos en Ventana Deslizante
Una cola monótona es una estructura de datos que permite encontrar el máximo (o mínimo) en una ventana deslizante de tamaño fijo en tiempo amortizado \\(O(1)\\) por elemento. Mantiene índices (o valores) de tal manera que los elementos de la cola están ordenados de forma monótona (creciente o decreciente). Para encontrar el máximo, la cola almacena los índices de los elementos en orden decreciente de sus valores correspondientes.
Consideremos un ejemplo simple para encontrar el máximo en cada ventana de tamaño \\(W\\) en un arreglo data\_array:
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm> // Para std::max
void encontrar_maximos_ventana(const std::vector<int>& arr_datos, int tam_ventana) {
if (tam_ventana <= 0 || tam_ventana > arr_datos.size()) {
return; // Ventana inválida
}
std::deque<int> indices_en_cola; // Almacena índices de arr_datos
std::cout << "Maximos de ventana deslizante de tamanio " << tam_ventana << ": ";
for (int i = 0; i < arr_datos.size(); ++i) {
// 1. Eliminar índices del frente si están fuera de la ventana actual
if (!indices_en_cola.empty() && indices_en_cola.front() <= i - tam_ventana) {
indices_en_cola.pop_front();
}
// 2. Eliminar índices de la parte trasera cuyos valores son menores o iguales al actual
// Esto asegura que la cola mantenga los valores en orden decreciente desde el frente
while (!indices_en_cola.empty() && arr_datos[indices_en_cola.back()] <= arr_datos[i]) {
indices_en_cola.pop_back();
}
// 3. Añadir el índice actual a la parte trasera de la cola
indices_en_cola.push_back(i);
// 4. Si la ventana se ha formado completamente (i.e., hemos procesado al menos 'tam_ventana' elementos)
if (i >= tam_ventana - 1) {
// El elemento en el frente de la cola es el índice del máximo en la ventana actual
std::cout << arr_datos[indices_en_cola.front()] << " ";
}
}
std::cout << std::endl;
}
// int main() {
// std::vector<int> ejemplo_arr = {1, 3, -1, -3, 5, 3, 6, 7};
// int ejemplo_k = 3;
// encontrar_maximos_ventana(ejemplo_arr, ejemplo_k); // Output: 3 3 5 5 6 7
// return 0;
// }
Solución Final con DP y Cola Monótona
Aplicando la lógica de la cola monótona a la transición de DP, el algoritmo completo sería:
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm> // Para std::max
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_elementos, K_limite;
std::cin >> N_elementos >> K_limite;
std::vector<long long> valores(N_elementos + 1); // Usamos 1-indexing
for (int i = 1; i <= N_elementos; ++i) {
std::cin >> valores[i];
}
// Calcular sumas de prefijo
std::vector<long long> sumas_prefijas(N_elementos + 1, 0);
for (int i = 1; i <= N_elementos; ++i) {
sumas_prefijas[i] = sumas_prefijas[i - 1] + valores[i];
}
// Definir estados de DP
std::vector<long long> dp_excluye(N_elementos + 1, 0); // a[i] no elegido
std::vector<long long> dp_incluye(N_elementos + 1, 0); // a[i] elegido
std::deque<int> indices_cola_mono; // Almacena índices 'j' para maximizar (dp_excluye[j] - sumas_prefijas[j])
// Caso base: un estado virtual en el índice 0 con suma 0
// Esto permite que el primer elemento (a[1]) sea el inicio de un bloque.
// El valor a maximizar para j=0 es (dp_excluye[0] - sumas_prefijas[0]) = 0 - 0 = 0.
indices_cola_mono.push_back(0);
for (int i = 1; i <= N_elementos; ++i) {
// Transición para dp_excluye[i]
dp_excluye[i] = std::max(dp_excluye[i - 1], dp_incluye[i - 1]);
// Limpiar la cola monótona: eliminar índices 'j' que están fuera de la ventana [i-K_limite, i-1]
// i - (j+1) + 1 <= K_limite => i - j <= K_limite => j >= i - K_limite
while (!indices_cola_mono.empty() && indices_cola_mono.front() < i - K_limite) {
indices_cola_mono.pop_front();
}
// Transición para dp_incluye[i]
// dp_incluye[i] = S[i] + max_{j} (dp_excluye[j] - S[j])
// El mejor 'j' está en el frente de la cola
int indice_mejor_j = indices_cola_mono.front();
dp_incluye[i] = (dp_excluye[indice_mejor_j] - sumas_prefijas[indice_mejor_j]) + sumas_prefijas[i];
// Añadir el índice actual 'i' a la cola monótona para futuras iteraciones
// El valor a considerar es (dp_excluye[i] - sumas_prefijas[i])
long long valor_actual_para_cola = dp_excluye[i] - sumas_prefijas[i];
while (!indices_cola_mono.empty() &&
(dp_excluye[indices_cola_mono.back()] - sumas_prefijas[indices_cola_mono.back()]) <= valor_actual_para_cola) {
indices_cola_mono.pop_back();
}
indices_cola_mono.push_back(i);
}
// La respuesta final es el máximo entre elegir o no el último elemento
std::cout << std::max(dp_excluye[N_elementos], dp_incluye[N_elementos]) << std::endl;
return 0;
}