Circular Barn Revisited

Explicación

El problema pide la cantidad mínima de distancia que las vacas necesitan recorrer para un granero circular. Sin embargo, si fijamos la posición de la primera puerta, el problema se puede reducir a un granero lineal $\texttt{rooms}[1..n]$ donde colocamos la primera puerta al comienzo de nuestro granero lineal. En ese caso, podemos definir $\texttt{dp}[i][j]$ como la suma de distancias para llenar las habitaciones $[j, n]$ si colocamos la $i$ -ésima puerta en $j$ . Todos los valores del arreglo $\texttt{dp}$ se inicializan con infinito. Además fijamos $\texttt{dp}[0][n+1] = 0$ porque sin puertas el único caso en que la distancia es cero es no llenar ninguna habitación. Nuestras transiciones serían entonces

$\texttt{dp}[i][j] = min(\texttt{dp}[i][j], \sum_{p=j+1}^{n+1} (p-j-1) \cdot \texttt{rooms}[p-1] + \texttt{dp}[i-1][p])$ ,

donde $i \in [1,k]$ y $j \in [1,n]$ . En otras palabras, $dp[i][j]$ es el mínimo de todas las distancias si ponemos la $i$ -ésima puerta en $j$ con la última puerta colocada en algún lugar $p$ después de $j$ . Esta distancia se calcula sumando la distancia para llenar las habitaciones $[j, p)$ a la cantidad óptima de distancia para llenar las habitaciones $[p, n]$ con $i-1$ puertas. $\texttt{dp}[k][0]$ representa la cantidad mínima de distancia necesaria si colocamos la primera puerta al comienzo del arreglo actual $\texttt{rooms}$ . Luego empezamos desde la segunda puerta moviendo la primera habitación $\texttt{rooms}[0]$ al final del arreglo y hacemos la DP de nuevo.

Nuestra respuesta sería la distancia mínima entre todas las posiciones posibles para la primera puerta.

Hay $n$ puertas que se pueden elegir como primera puerta. En cada DP, agregamos cada vez una de las $k$ puertas e iteramos por cada una de las $n$ posiciones para colocarla. Para cada una de estas posiciones, recorremos todas las $n$ colocaciones posibles de la última puerta y calculamos el resultado óptimo para nuestra posición actual con la nueva puerta. Esto da una complejidad temporal total de $\mathcal{O}(k n^3)$ , que es suficientemente rápida para las restricciones dadas.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("cbarn2.in", "r", stdin);
	freopen("cbarn2.out", "w", stdout);
 
	int n, k;
	cin >> n >> k;
	deque<int> rooms(n);
	for (int &r : rooms) { cin >> r; }
 
	long long min_dist = INT64_MAX;
	// Iterar sobre todas las posiciones posibles de la primera puerta
	for (int start_pos = 0; start_pos < n; start_pos++) {
		vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, INT64_MAX));
		// Sin puertas usadas, la distancia es cero solo si no hay habitación
		// llena
		dp[0][n] = 0;
		// Iterar sobre la cantidad de puertas usadas
		for (int used_door = 1; used_door <= k; used_door++) {
			// Iterar sobre todas las posiciones posibles para colocar esta nueva puerta
			for (int i = 0; i < n; i++) {
				// partial_dist almacena la suma de distancias para llenar las
				// habitaciones [i, j - 1]
				long long partial_dist = 0;
				/*
				 * Iterar sobre todas las colocaciones posibles de la última puerta
				 * y encontrar el mínimo si usamos esta colocación con nuestra nueva
				 * puerta en i
				 */
				for (int j = i + 1; j <= n; j++) {
					// Sumar la cantidad de distancia necesaria para llenar la nueva
					// habitación en j - 1
					partial_dist += rooms[j - 1] * (j - i - 1);
					long long new_dist = dp[used_door - 1][j];
					if (new_dist < INT64_MAX) { new_dist += partial_dist; }
					dp[used_door][i] = min(dp[used_door][i], new_dist);
				}
			}
		}
		// Actualizar la mejor respuesta usando la respuesta actual de dp
		min_dist = min(min_dist, dp[k][0]);
		/*
		 * Poner la primera habitación al final del deque para que la primera
		 * puerta se coloque en la segunda habitación
		 */
		int first_room = rooms.front();
		rooms.pop_front();
		rooms.push_back(first_room);
	}
 
	cout << min_dist << endl;
}