1. Fundamentos de la Monotonía de Decisión
1.1 Desigualdad de Cuadrilátero
Se define una función de costo \(w(i, j)\) que satisface la desigualdad de cuadrilátero si para todo \(a \le b \le c \le d\), se cumple la siguiente relación:
\[w(a, d) + w(b, c) \ge w(a, c) + w(b, d)\]
Intuitivamente, esto significa que el costo de un intervalo que contiene a otro, sumado al costo del intervalo contenido, es mayor o igual a la suma de los costos de dos intervalos que se intersectan. Una forma alternativa y más práctica para verificar esta propiedad es comprobar que para cualquier \(a < b\):
\[w(a, b+1) + w(a+1, b) \ge w(a, b) + w(a+1, b+1)\]
1.2 Monotonía de Decisión
Consideremos un problema clásico de programación dinámica 1D/1D donde queremos minimizar el costo de partición de una secuencia:
\[f_i = \min_{0 \le j < i} \{ f_j + w(j, i) \}\]
Sea \(p_i\) el índice \(j\) que minimiza la expresión para \(f_i\), conocido como el punto de decisión óptimo. Si se cumple que \(p_i \le p_{i+1}\) para todo \(i\), decimos que el problema posee monotonía de decisión. Un teorema fundamental establece que: si \(w\) satisface la desigualdad de cuadrilátero, entonces \(f\) posee monotonía de decisión.
Esta propiedad permite optimizar la complejidad de \(O(n^2)\) a \(O(n \log n)\) o incluso \(O(n)\) en ciertos escenarios.
2. Técnicas de Optimización
2.1 Cola con Búsqueda Binaria (Binary Search Queue)
Dado que los puntos de decisión \(p_i\) son no decrecientes, para cada punto de origen \(x\), existirá un rango contiguo \([l_x, r_x]\) en el cual \(x\) es la mejor decisión para todos los \(f_i\) con \(i \in [l_x, r_x]\).
Mantenemos una estructura de datos (usualmente una deque) que almacene ternas \((p, l, r)\), donde \(p\) es el punto de decisión y \([l, r]\) es el intervalo donde es óptimo. Al procesar un nuevo índice \(i\):
- Eliminamos los elementos al frente de la cola cuyo rango de validez \(r\) sea menor que \(i\).
- Calculamos \(f_i\) usando el punto de decisión al frente de la cola.
- Para insertar \(i\) como posible decisión futura, comparamos con el final de la cola. Si \(i\) es mejor que el punto de decisión actual en todo el rango \([l, n]\), eliminamos el final de la cola y repetimos. Si no, usamos búsqueda binaria para encontrar el punto exacto donde \(i\) empieza a ser mejor que la decisión anterior.
struct Decision {
int origen, inicio, fin;
};
void optimizar_cola(int n) {
deque<Decision> dq;
dq.push_back({0, 1, n});
for (int i = 1; i <= n; ++i) {
// Eliminar decisiones obsoletas
while (!dq.empty() && dq.front().fin < i) dq.pop_front();
int p_optimo = dq.front().origen;
f[i] = calcular_costo(p_optimo, i);
// Insertar la nueva decisión i
while (!dq.empty() && comparar_decisiones(i, dq.back().origen, dq.back().inicio)) {
dq.pop_back();
}
if (dq.empty()) {
dq.push_back({i, i + 1, n});
} else {
int pos_corte = buscar_binaria(dq.back().origen, i, dq.back().inicio, dq.back().fin);
dq.back().fin = pos_corte - 1;
if (pos_corte <= n) dq.push_back({i, pos_corte, n});
}
}
}
2.2 Divide y Vencerás (Offline)
Este método es aplicable cuando el cálculo de \(f_i\) en la capa actual solo depende de valores de una capa anterior (DP 2D/1D), de la forma:
\[f_{i, j} = \min_{k < j} \{ f_{i-1, k} + w(k, j) \}\]
La función recursiva solve(L, R, optL, optR) calcula los valores de \(f_{i, j}\) para \(j \in [L, R]\), sabiendo que sus decisiones óptimas se enucentran en \([optL, optR]\).
void dividir_y_vencer(int capa, int L, int R, int optL, int optR) {
if (L > R) return;
int mid = (L + R) / 2;
int mejor_p = -1;
long long mejor_valor = INF;
for (int k = optL; k <= min(mid, optR); ++k) {
long long valor_actual = dp[capa-1][k] + costo(k + 1, mid);
if (valor_actual < mejor_valor) {
mejor_valor = valor_actual;
mejor_p = k;
}
}
dp[capa][mid] = mejor_valor;
dividir_y_vencer(capa, L, mid - 1, optL, mejor_p);
dividir_y_vencer(capa, mid + 1, R, mejor_p, optR);
}
2.3 Divide y Vencerás para DP Online
En problemas donde \(f_i\) depende de valores de \(f_j\) ya calculados en la misma capa, pero el costo \(w\) requiere un movimiento de punteros (estilo algoritmo de Mo), se puede emplear una variante de Divide y Vencerás. Se divide el intervalo \([l, r]\) y se calculan las contribuciones de la mitad izquierda a la mitad derecha, procesando recursivamente para mantener la validez de los datos calculados.
3. Casos de Aplicación
Ejemplo 1: El Poeta Pequeño G
El problema requiere minimizar una función de costo de la forma \(|sl_i - sl_j + i - j - 1 - L|^P\). Al demostrar que esta función cumple la desigualdad de cuadrilátero, podemos aplicar la Cola con Búsqueda Binaria para resolverlo en \(O(n \log n)\).
Ejemplo 2: Minimización de Costos en Rangos (CF868F)
En este caso, el costo \(w(l, r)\) es el número de pares de elementos iguales en el subsegmento. Como este costo no tiene una fórmula cerrada simple pero se puede actualizar moviendo punteros \(l\) y \(r\), la técnica de Divide y Vencerás Offline es ideal. El movimiento total de los punteros a través de los niveles de recursión se mantiene en \(O(n \log n)\).
4. Monotonía en Programación Dinámica de Intervalos
Para problemas de DP de intervalos con la forma:
\[f_{i, j} = \min_{i \le k < j} \{ f_{i, k} + f_{k+1, j} \} + w(i, j)\]
Si \(w\) cumple con la desigualdad de cuadrilátero y es monótona respecto a la inclusión de intervalos (\(w(b, c) \le w(a, d)\) para \([b, c] \subseteq [a, d]\)), entonces el punto de decisión óptimo \(p_{i, j}\) satisface:
\[p_{i, j-1} \le p_{i, j} \le p_{i+1, j}\]
Esto permite reducir la complejidad de \(O(n^3)\) a \(O(n^2)\) al limitar el rango de búsqueda de \(k\).
for (int len = 2; len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
for (int k = p[i][j-1]; k <= p[i+1][j]; ++k) {
long long val = f[i][k] + f[k+1][j] + w(i, j);
if (val < f[i][j]) {
f[i][j] = val;
p[i][j] = k;
}
}
}
}