USACO Gold 2016 December - Cow Checklist

Official Analysis (Java)

Note that at any single point in time Farmer John will be at either a Holstein or a Guernsey, and will have the choice to either go to the next Holstein or Guernsey.

This suggests a DP. Let $\texttt{dp}_{i,j}$ represent the minimum cumulative distance for Farmer John to visit the first $i$ Holsteins and the first $j$ Guernseys. *

Then, Farmer John can either go to the next Holstein or the next Guernsey.

$\texttt{dp}_{i, j} = \min(\texttt{dp}_{i - 1,j}, \texttt{dp}_{i,j - 1})$

Implementation

Time Complexity: $\mathcal{O}(H \cdot G)$

Copy
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

const ll MAX_D = 1e18;
struct Coord {
  public: