We can start by writing a brute force algorithm that tries to enumerate all possible valid configurations of crosswalks. If we think about how to build this up in a brute force manner, we could start by considering the cow in field $N$ on the top side. We could either build a crosswalk with it or ignore it. If we ignore it, then we have to consider the leftmost $N-1$ fields on the top side and the leftmost $N$ fields on the right side. If we do build a crosswalk though, we should use the rightmost field that would still be a valid crosswalk. After building it, we have the leftmost $N-1$ fields in the top side and, assuming that the crosswalk goes to field $i$ on the bottom side, the leftmost $i-1$ fields on the bottom side.

There could be exponentially many configurations of crosswalks, but for a fixed pair $(a, b)$ of having the leftmost $a$ fields on the top side and leftmost $b$ fields on the bottom side available for building crosswalks, we just have to maintain the maximum number of crosswalks that can be built using just those fields.

Here is Brian Dean's code, which does this iteratively instead of recursively.

#include <iostream> #include <fstream> #include <algorithm> using namespace std; int N; int A[1000][1000]; int S[1000], T[1000]; int main(void) { ifstream fin("nocross.in"); ofstream fout("nocross.out"); fin >> N; for (int i=0; i<N; i++) fin >> S[i]; for (int i=0; i<N; i++) fin >> T[i]; A[0][0] = abs(S[0]-T[0])<=4; for (int i=1; i<N; i++) A[i][0] = max(A[i-1][0], (int)(abs(S[i]-T[0]) <= 4)); for (int i=1; i<N; i++) A[0][i] = max(A[0][i-1], (int)(abs(S[0]-T[i]) <= 4)); for (int i=1; i<N; i++) for (int j=1; j<N; j++) A[i][j] = max( max(A[i-1][j], A[i][j-1]), A[i-1][j-1]+(abs(S[i]-T[j])<=4)); fout << A[N-1][N-1] << "\n"; return 0; }