The Stables of Genghis Khan

Solución

Definamos $\texttt{lowestOps}[a][b]$ como el número mínimo de operaciones para ver si cada caballo está en los establos o no, dado que solo consideramos los caballos en el intervalo $(\texttt{stableHorses[a]}, \texttt{stableHorses[b]})$ , donde $\texttt{stableHorses}$ es una lista ordenada de todos los caballos que están en los establos.

¿Por qué usar un intervalo abierto? Es para contemplar los caballos cuyos IDs no están contenidos en el rango de IDs de los caballos del establo. Por ejemplo, si tuviéramos un caballo con ID $4$ , y los caballos en los establos fueran $[6, 7, 10]$ , entonces $\texttt{lowestOps}$ no tendría forma de contemplar ese caballo.

Para resolverlo, podemos agregar dos caballos hipotéticos que quedan justo fuera de los límites de todos los demás: uno al principio y otro al final. Esto, junto con el intervalo abierto, garantiza que podemos contemplar todos los caballos excepto los hipotéticos que agregamos.

Luego, para calcular el valor de un intervalo, recorremos todas las raíces posibles que podemos usar para el árbol de ese intervalo. Si estamos calculando $\texttt{lowestOps}[a][b]$ con $b-a\geq3$ y usamos una raíz $c$ ( $a<c<b$ ), entonces tenemos la siguiente relación de recurrencia:

\texttt{lowestOps}[a][b]=\texttt{lowestOps}[a][c]+\texttt{lowestOps}[c][b]+(\texttt{stableHorses}[b]-\texttt{stableHorses}[a]-1)

Implementación

Complejidad temporal: $\mathcal{O}(N^3)$

C++JavaPython


#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int horse_num;
	int stable_num;
	std::cin >> horse_num >> stable_num;
	vector<int> stable_horses(stable_num);
	for (int &h : stable_horses) {
		std::cin >> h;
		assert(0 < h && h <= horse_num);
	}
	// agregamos dos caballos "fuera de rango"
	stable_horses.push_back(0);
	stable_horses.push_back(horse_num + 1);
 
	std::sort(stable_horses.begin(), stable_horses.end());
 
	/*
	 * lowest_ops[i][j] = mín. operaciones si solo consideramos caballos
	 * que existen en el intervalo de índices (i, j)
	 * ej: lowest_ops[1][4] y stable_horses = [0, 1, 3, 7, 10, 11]
	 *     significa que solo consideramos caballos de (1, 10)
	 */
	vector<vector<int>> lowest_ops(stable_num + 2,
	                               vector<int>(stable_num + 2, INT32_MAX));
	for (int i = 0; i < stable_num + 2; i++) {
		lowest_ops[i][i] = 0;
		if (i + 1 < stable_num + 2) {
			lowest_ops[i][i + 1] = stable_horses[i + 1] - stable_horses[i] - 1;
		}
		if (i + 2 < stable_num + 2) {
			lowest_ops[i][i + 2] = stable_horses[i + 2] - stable_horses[i] - 1;
		}
	}
	for (int num = 4; num <= stable_num + 2; num++) {
		for (int start = 0; start + num - 1 < stable_num + 2; start++) {
			int end = start + num - 1;
			/*
			 * primero manejamos los casos borde de inicio y fin,
			 * donde el elemento más pequeño o el más grande se volvió la raíz
			 */
			lowest_ops[start][end] =
			    std::min(lowest_ops[start][end],
			             lowest_ops[start][start + 1] + lowest_ops[start + 1][end] +
			                 stable_horses[end] - stable_horses[start + 1]);
			lowest_ops[start][end] =
			    std::min(lowest_ops[start][end],
			             lowest_ops[end - 1][end] + lowest_ops[start][end - 1] +
			                 stable_horses[end - 1] - stable_horses[start]);
 
			/*
			 * luego pasamos a la parte real en la que combinamos
			 * dos partes con top como raíz
			 */
			for (int top = start + 2; top < end - 1; top++) {
				lowest_ops[start][end] =
				    std::min(lowest_ops[start][end],
				             lowest_ops[start][top] + lowest_ops[top][end] +
				                 stable_horses[end] - stable_horses[start] - 1);
			}
		}
	}
	cout << lowest_ops[0][stable_num + 1] << endl;
}


import java.io.*;
import java.util.Arrays;
 
public final class genghis {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int horseNum = Integer.parseInt(read.readLine());
		int stableNum = Integer.parseInt(read.readLine());
		int[] stableHorses = new int[stableNum + 2];
		for (int i = 1; i <= stableNum; i++) {
			stableHorses[i] = Integer.parseInt(read.readLine());
			if (stableHorses[i] < 1 || horseNum < stableHorses[i]) {
				throw new IllegalArgumentException("this horse shouldn't exist");
			}
		}
		// agregamos los caballos "fuera de rango"
		stableHorses[0] = 0;
		stableHorses[stableNum + 1] = horseNum + 1;
		Arrays.sort(stableHorses);
 
		/*
		 * lowestOps[i][j] = mín. operaciones si solo consideramos caballos
		 * que existen en el intervalo de índices (i, j)
		 * ej: lowestOps[1][4] y stable_horses = [0, 1, 3, 7, 10, 11]
		 *     significa que solo consideramos caballos de (1, 10)
		 */
		int[][] lowestOps = new int[stableNum + 2][stableNum + 2];
		for (int i = 0; i < stableNum + 2; i++) {
			Arrays.fill(lowestOps[i], Integer.MAX_VALUE);
			lowestOps[i][i] = 0;
			if (i + 1 < stableNum + 2) {
				lowestOps[i][i + 1] = stableHorses[i + 1] - stableHorses[i] - 1;
			}
			if (i + 2 < stableNum + 2) {
				lowestOps[i][i + 2] = stableHorses[i + 2] - stableHorses[i] - 1;
			}
		}
		for (int num = 4; num <= stableNum + 2; num++) {
			for (int start = 0; start + num - 1 < stableNum + 2; start++) {
				int end = start + num - 1;
				/*
				 * primero manejamos los casos borde de inicio y fin,
				 * donde el elemento más pequeño o el más grande se volvió la raíz
				 */
				lowestOps[start][end] =
				    Math.min(lowestOps[start][end],
				             lowestOps[start][start + 1] + lowestOps[start + 1][end] +
				                 stableHorses[end] - stableHorses[start + 1]);
				lowestOps[start][end] =
				    Math.min(lowestOps[start][end],
				             lowestOps[end - 1][end] + lowestOps[start][end - 1] +
				                 stableHorses[end - 1] - stableHorses[start]);
 
				/*
				 * luego pasamos a la parte real en la que combinamos
				 * dos partes con top como raíz
				 */
				for (int top = start + 2; top < end - 1; top++) {
					lowestOps[start][end] =
					    Math.min(lowestOps[start][end],
					             lowestOps[start][top] + lowestOps[top][end] +
					                 stableHorses[end] - stableHorses[start] - 1);
				}
			}
		}
		System.out.println(lowestOps[0][stableNum + 1]);
	}
}


horse_num = int(input())
stable_num = int(input())
stable_horses = sorted([0, horse_num + 1] + [int(input()) for _ in range(stable_num)])
 
"""
lowest_ops[i][j] = mín. operaciones si solo consideramos caballos
que existen en el intervalo de índices (i, j)
ej: lowest_ops[1][4] y stable_horses = [0, 1, 3, 7, 10, 11]
	significa que solo consideramos caballos de (1, 10)
"""
lowest_ops = [
	[float("inf") for _ in range(stable_num + 2)] for _ in range(stable_num + 2)
]
for i in range(stable_num + 2):
	lowest_ops[i][i] = 0
	if i + 1 < stable_num + 2:
		lowest_ops[i][i + 1] = stable_horses[i + 1] - stable_horses[i] - 1
	if i + 2 < stable_num + 2:
		lowest_ops[i][i + 2] = stable_horses[i + 2] - stable_horses[i] - 1
 
for num in range(4, stable_num + 2 + 1):
	for start in range(0, (stable_num + 2) - (num - 1)):
		end = start + num - 1
		"""
		primero manejamos los casos borde de inicio y fin,
		donde el elemento más pequeño o el más grande se volvió la raíz
		"""
		lowest_ops[start][end] = min(
			lowest_ops[start][end],
			lowest_ops[start][start + 1]
			+ lowest_ops[start + 1][end]
			+ stable_horses[end]
			- stable_horses[start + 1],
		)
		lowest_ops[start][end] = min(
			lowest_ops[start][end],
			lowest_ops[end - 1][end]
			+ lowest_ops[start][end - 1]
			+ stable_horses[end - 1]
			- stable_horses[start],
		)
 
		"""
		luego pasamos a la parte real en la que combinamos
		dos partes con top como raíz
		"""
		for top in range(start + 2, end - 1):
			lowest_ops[start][end] = min(
				lowest_ops[start][end],
				lowest_ops[start][top]
				+ lowest_ops[top][end]
				+ stable_horses[end]
				- stable_horses[start]
				- 1,
			)
 
print(lowest_ops[0][stable_num + 1])