Divide y vencerás - DP

Visión general

Considerar un problema de programación dinámica con la siguiente fórmula

donde $C(i,j)$ es una función de costo y se puede calcular en tiempo $O(1)$. Además, $dp(i,j) =0$ para $j<0$.

La implementación directa da un tiempo de ejecución de $O(mn^2)$ si $0\leq i < m$ y $0\leq j < n$. La DP de divide y vencerás permite optimizarlo a $O(mn \log n)$.

Para cada $i,j$, sea $\text{opt}(i,j)$ el valor de $k$ que minimiza el lado derecho de la ecuación. La DP de divide y vencerás solo aplica si

A menudo, demostrar esto con la función de costo dada es difícil, pero si la función de costo satisface la desigualdad del cuadrángulo , la condición se cumple.

Entonces podemos aplicar la idea de divide y vencerás. Fijar un $i$ dado. Primero, calcular $\text{opt}(i,n/2)$. Luego calcular $\text{opt}(i, n/4)$ usando el hecho de que es menor o igual que $\text{opt}(i, n/2)$. De forma análoga, podemos calcular $\text{opt}(i, 3n/4)$ y partir recursivamente los rangos a la mitad, llevando las cotas inferior y superior. Ver el código de abajo para más detalles.

Para empezar a analizar la complejidad de divide y vencerás, primero observar que hay $O(\log{n})$ niveles en la recursión. Afirmamos que se hacen $O(n)$ pasos en cada nivel. Sea $S_k$ la longitud total de los intervalos de $\text{opt}$ (denotados por $rl$ y $rr$ en el código) en el $k$-ésimo nivel, y observar que cada vez que un intervalo del nivel $k$ de longitud $l$ se parte, el intervalo (o los intervalos) resultante tiene longitud total a lo sumo $l + 1$. Además, en el nivel $k$ se realizan a lo sumo $2^k$ particiones, así que $S_{k + 1} \leq S_k + 2^k$. Aplicando la cota por inducción con $S_0 = n$ se obtiene que para cada nivel $k$,

Así, la complejidad de cada divide y vencerás es $O(n\log{n})$, y la complejidad de todo el cálculo de la DP es $O(mn\log{n})$.

Ejemplo - Circular Barn

Ya se debería conocer la solución con CHT.

Explicación

Iteramos sobre las posibilidades de la ubicación de la primera puerta. Para cada una de las primeras puertas, ahora podemos ver el establo de forma lineal. Todos los cálculos posteriores se hacen suponiendo que el establo es una secuencia lineal de puertas que empieza en la primera puerta abierta.

Sea $dp(i,k)$ la ubicación de la última puerta si colocamos $k$ puertas de forma óptima entre las primeras $i$ habitaciones. La idea es que $dp(i,k) \leq dp(i+1, k)$. Supongamos, por contradicción, que esto no es cierto. Entonces $dp(i,k) > dp(i+1,k)$, así que también $dp(i+1,k) \leq i$. Pero entonces podríamos haber usado la mejor configuración posible para $(i+1,k)$ también en la configuración $(i,k)$, ya que todas las puertas abiertas están de todos modos entre las primeras $i$ habitaciones.

Como se cumple la condición de monotonía, ahora podemos aplicar DP de divide y vencerás. Fijar el valor de $k$ y calcular $dp(n/2, k)$. Luego calcularlo para las mitades izquierda y derecha del arreglo.

Implementación

Complejidad temporal: $\mathcal{O}(n^2 k \log n)$, ya que hay que revisar $n$ habitaciones para la posición óptima del primer establo.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const int MAX_N = 1000;
const int MAX_K = 7;
 
// calc[i][j] stores the # of steps to get all cows distance j away to door i
// to make implementing a cyclic array easier, we double the size
vector<vector<ll>> calc(2 * MAX_N, vector<ll>(MAX_N + 1, 0));
// dp[i][j] stores the answer for doors 0,1,.., j and i doors open
vector<vector<ll>> dp(MAX_K + 1, vector<ll>(MAX_N + 1, INT64_MAX));
 
int rot;
 
void compdp(int k, int begin, int end, int rl, int rr) {
	// fixed k, begin and end are the ends of the array, rl and rr are the
	// bounds on the last door used
	int mid = (begin + end) / 2;
 
	ll best = INT64_MAX;
	int best_last = -1;
	// best is min amount moved, last is the last door used
	for (int last = rl; last <= min(mid, rr); last++) {
		ll cost = dp[k - 1][last - 1] + calc[last + rot][mid - last + 1];
		if (cost < best) {
			best = cost;
			best_last = last;
		} else if (cost == best && last < best_last) {
			best_last = last;
		}
	}
	dp[k][mid] = best;
	if (begin == end) { return; }
	compdp(k, begin, mid, rl, best_last);
	compdp(k, mid + 1, end, best_last, rr);
}
 
int main() {
	freopen("cbarn.in", "r", stdin);
	int n, k;
	cin >> n >> k;
 
	vector<int> a(2 * n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i + n] = a[i];
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			calc[i][j] = calc[i + n][j] = calc[i][j - 1] + (ll)a[i + j - 1] * (j - 1);
		}
	}
 
	// rotate stores where we start in the linear representation
	ll ans = INT64_MAX;
	for (rot = 0; rot < n; rot++) {
		for (int i = 0; i < n; i++) { dp[0][i] = calc[rot][i + 1]; }
		for (int i = 1; i < k; i++) {
			for (int j = 0; j < n; j++) { dp[i][j] = INT64_MAX; }
			compdp(i, i, n - 1, i, n - 1);
		}
		ans = min(ans, dp[k - 1][n - 1]);
	}
 
	freopen("cbarn.out", "w", stdout);
	cout << ans << endl;
}

Problemas

Enunciado en inglés de JOI Bubblesort: Se da un arreglo de longitud $N$ $(1 \le N \le 100,000)$. Hay que elegir dos números de este arreglo e intercambiarlos. Después de intercambiar esos dos números, se ordena el arreglo usando un algoritmo de ordenamiento de burbuja. ¿Cuál es el número mínimo de intercambios del bubble sort necesarios, suponiendo que se eligen de forma óptima los dos números iniciales a intercambiar? Los dos números iniciales que se intercambian no cuentan hacia el número mínimo de intercambios del bubble sort.