Skip to Content
CTRL K

The Cow Run

Análisis oficial (C++) 

Explicación

Cuando vamos de un punto a otro, es óptimo recoger todas las vacas en el camino, así que la lista de vacas que visitamos siempre formará un subarreglo en la lista ordenada de todas las vacas.

Así que ordenamos las vacas por su posición.

Sin embargo, la solución óptima también podría involucrar ir de un lado al otro. Para contemplar esto, usamos DP de rangos.

Estados

Tenemos que llevar la cuenta de las vacas que ya recogimos. Como esto siempre será un rango, lo representamos como ii y jj (los extremos del intervalo).

También tenemos que llevar la cuenta de en qué lado estamos (kk).

dp[i][j][k]=\texttt{dp}[i][j][k] = \hspace{0.1cm}costo mínimo para visitar todas estas vacas.

La respuesta será el mínimo de cada lado al considerar el rango completo.

Casos base

Si solo visitamos la vaca ii, entonces nos costará pos[i]⋅n\texttt{pos}[i] \cdot n porque cada otra vaca seguirá costándonos dinero mientras vamos a detener esa vaca.

Transiciones

Hay cuatro casos posibles. Aquí, k=0k=0 significa que Farmer John está a la izquierda del intervalo, y k=1k=1 significa que Farmer John está a la derecha.

dp[i][j][0]=min⁡(dp[i+1][j][0]+∣x[i+1]−x[i]∣⋅remaining,dp[i+1][j][1]+∣x[i]−x[j]∣⋅remaining)\texttt{dp}[i][j][0] = \min(\texttt{dp}[i + 1][j][0] + |x[i + 1] - x[i]| \cdot \texttt{remaining}, \texttt{dp}[i + 1][j][1] + |x[i] - x[j]| \cdot \texttt{remaining}) dp[i][j][1]=min⁡(dp[i][j−1][1]+∣x[j−1]−x[j]∣⋅remaining,dp[i][j−1][0]+∣x[i]−x[j]∣⋅remaining)\texttt{dp}[i][j][1] = \min(\texttt{dp}[i][j - 1][1] + |x[j - 1] - x[j]| \cdot \texttt{remaining}, \texttt{dp}[i][j - 1][0] + |x[i] - x[j]| \cdot \texttt{remaining})

Para cada lado, tenemos que considerar si continuar en la misma dirección o visitar la siguiente vaca en el extremo opuesto.

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("cowrun.in", "r", stdin);
	freopen("cowrun.out", "w", stdout);
 
	int n;
	cin >> n;
 
	vector<int> pos(n);
	for (int i = 0; i < n; i++) { cin >> pos[i]; }
 
	sort(pos.begin(), pos.end());
 
	/*
	 * dp[i][j][k] = costo mínimo de visitar todas las vacas dentro del rango
	 * i = extremo izquierdo (inclusivo)
	 * j = extremo derecho (inclusivo)
	 * k (0/1) = lado actual
	 */
	vector<vector<vector<int>>> dp(
	    n + 1, vector<vector<int>>(n + 1, vector<int>(2, INT32_MAX)));
 
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i; j < n; j++) {
			if (i == j) {
				dp[i][j][0] = abs(pos[i]) * n;
				dp[i][j][1] = abs(pos[j]) * n;
			} else {
				// la cantidad de vacas sobre las que se inflige el costo
				int remaining = n - (j - i);
 
				// considerar si queremos ir al mismo lado o al lado opuesto
				if (i < n) {
					dp[i][j][0] =
					    min(dp[i + 1][j][0] + (abs(pos[i + 1] - pos[i]) * remaining),
					        dp[i + 1][j][1] + (abs(pos[j] - pos[i]) * remaining));
				}
 
				if (j > 0) {
					dp[i][j][1] =
					    min(dp[i][j - 1][1] + (abs(pos[j - 1] - pos[j]) * remaining),
					        dp[i][j - 1][0] + (abs(pos[j] - pos[i]) * remaining));
				}
			}
		}
	}
 
	cout << min(dp[0][n - 1][0], dp[0][n - 1][1]) << endl;
}
import java.io.*;
import java.util.*;
 
public class CowRun {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("cowrun.in"));
		int n = Integer.parseInt(br.readLine());
 
		int[] pos = new int[n];
		for (int i = 0; i < n; i++) { pos[i] = Integer.parseInt(br.readLine()); }
		Arrays.sort(pos);
 
		/*
		 * dp[i][j][k] = costo mínimo de visitar todas las vacas dentro del rango
		 * i = extremo izquierdo (inclusivo)
		 * j = extremo derecho (inclusivo)
		 * k (0/1) = lado actual
		 */
		int[][][] dp = new int[n + 1][n + 1][2];
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < n + 1; j++) {
				dp[i][j][0] = Integer.MAX_VALUE;
				dp[i][j][1] = Integer.MAX_VALUE;
			}
		}
 
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i; j < n; j++) {
				if (i == j) {
					dp[i][j][0] = Math.abs(pos[i]) * n;
					dp[i][j][1] = Math.abs(pos[j]) * n;
				} else {
					// la cantidad de vacas sobre las que se inflige el costo
					int remaining = n - (j - i);
 
					// considerar si queremos ir al mismo lado o al lado opuesto
					dp[i][j][0] = Math.min(
					    dp[i + 1][j][0] + (Math.abs(pos[i + 1] - pos[i]) * remaining),
					    dp[i + 1][j][1] + (Math.abs(pos[j] - pos[i]) * remaining));
 
					dp[i][j][1] = Math.min(
					    dp[i][j - 1][1] + (Math.abs(pos[j - 1] - pos[j]) * remaining),
					    dp[i][j - 1][0] + (Math.abs(pos[j] - pos[i]) * remaining));
				}
			}
		}
 
		PrintWriter pw = new PrintWriter("cowrun.out");
		pw.println(Math.min(dp[0][n - 1][0], dp[0][n - 1][1]));
		pw.close();
	}
}
Fundamentos