USACO Gold 2017 February - Why Did the Cow Cross The Road II

Official Analysis (C++)

Explanation

Let's define $\texttt{dp}[i][j]$ as the maximum number of disjoint friendly crosswalks up to field $i$ on the first side of the road and field $j$ on the second side of the road. We can build a crosswalk between fields $i$ and $j$ as long as there isn't a crosswalk between fields $i$, $j - 1$ and $i - 1$, $j$. Thus, $\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))$, where $\texttt{id}[i]$ and $\texttt{id}[j]$ represent the breed IDs of the cows in the $i$-th and $j$-th fields, respectively.

The answer is $\texttt{dp}[N][N]$.

Implementation

Time Complexity: $\mathcal{O}(N ^ 2)$

Copy
#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);

Copy
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; }

Copy
with open("nocross.in") as read:
	n = int(read.readline().strip())

	"""
	id1 represents the breed ID of the fields
	on the first side of the road
	id2 represents the breed ID of the fields
	on the other side of the road.
	"""
	id1 = [0]