Skip to Content
CTRL K

Why Did the Cow Cross The Road II

Análisis oficial (C++) 

Explicación

Definamos dp[i][j]\texttt{dp}[i][j] como la cantidad máxima de cruces amistosos disjuntos hasta el campo ii del primer lado de la carretera y el campo jj del segundo lado de la carretera. Podemos construir un cruce entre los campos ii y jj siempre que no haya un cruce entre los campos ii, j−1j - 1 e i−1i - 1, jj. Así, dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1]+(∣id[i]−id[j]∣≤4))\texttt{dp}[i][j] = \max(\texttt{dp}[i - 1][j], \texttt{dp}[i][j - 1], \texttt{dp}[i - 1][j - 1] + (|\texttt{id}[i] - \texttt{id}[j]| \leq 4)), donde id[i]\texttt{id}[i] e id[j]\texttt{id}[j] representan los IDs de raza de las vacas en el ii-ésimo y jj-ésimo campo, respectivamente.

La respuesta es dp[N][N]\texttt{dp}[N][N].

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1000;
 
int dp[MAXN + 1][MAXN + 1];
 
int main() {
	freopen("nocross.in", "r", stdin);
	freopen("nocross.out", "w", stdout);
	int n;
	cin >> n;
	/*
	 * id1 representa el ID de raza de los campos
	 * del primer lado de la carretera
	 * id2 representa el ID de raza de los campos
	 * del otro lado de la carretera.
	 */
	vector<int> id1(n + 1), id2(n + 1);
	for (int i = 1; i <= n; i++) { cin >> id1[i]; }
	for (int i = 1; i <= n; i++) { cin >> id2[i]; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			/*
			 * Podemos o bien construir un nuevo cruce entre
			 * i y j o no construir un nuevo cruce.
			 */
			dp[i][j] = max({dp[i - 1][j], dp[i][j - 1],
			                dp[i - 1][j - 1] + (abs(id1[i] - id2[j]) <= 4)});
		}
	}
	cout << dp[n][n] << endl;
}
import java.io.*;
import java.util.*;
 
public class NoCross {
	static int[] firstSide;
	static int[] secondSide;
	static int[][] memoization;
 
	static boolean friendly(int cow1, int cow2) {
		if (Math.abs(firstSide[cow1] - secondSide[cow2]) <= 4) { return true; }
		return false;
	}
 
	static int solve(int n, int m) {
		if (n < 0 || m < 0) {  // caso base
			return 0;
		}
		// si ya está computado, solo devolver el valor
		if (memoization[n][m] != -1) { return memoization[n][m]; }
 
		if (friendly(n, m)) {  // son amistosas, conectar
			int answer = 1 + solve(n - 1, m - 1);
			memoization[n][m] = answer;
			return answer;
		}
		// podemos saltar o bien la vaca del lado izquierdo o la del lado derecho
		else {
			int answer = Math.max(solve(n - 1, m), solve(n, m - 1));
			memoization[n][m] = answer;
			return answer;
		}
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("nocross");
 
		int n = io.nextInt();
		firstSide = new int[n];
		secondSide = new int[n];
		memoization = new int[n][n];
 
		for (int[] memo : memoization) {  // llenar la matriz con -1
			Arrays.fill(memo, -1);
		}
		for (int x = 0; x < n; x++) { firstSide[x] = io.nextInt(); }
		for (int x = 0; x < n; x++) { secondSide[x] = io.nextInt(); }
		io.println(solve(n - 1, n - 1));
		io.close();
	}
	// CodeSnip{Kattio}
}
with open("nocross.in") as read:
	n = int(read.readline().strip())
 
	"""
	id1 representa el ID de raza de los campos
	del primer lado de la carretera
	id2 representa el ID de raza de los campos
	del otro lado de la carretera.
	"""
	id1 = [0]
	id2 = [0]
	for _ in range(n):
		x = int(read.readline().strip())
		id1.append(x)
	for _ in range(n):
		x = int(read.readline().strip())
		id2.append(x)
 
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		"""
		Podemos o bien construir un nuevo cruce entre
		i y j o no construir un nuevo cruce.
		"""
		dp[i][j] = max(
			dp[i - 1][j],
			dp[i][j - 1],
			dp[i - 1][j - 1] + (1 if abs(id1[i] - id2[j]) <= 4 else 0),
		)
 
print(dp[n][n], file=open("nocross.out", "w"))
Fundamentos