Analysis: The Cow Run by Neal Wu

We first sort the cows' positions in order, and we add a cow at location 0 for simplicity. A key observation is that at any time, the set of cows we have visited forms a consecutive sequence in the sorted list of cows. Thus, we can do DP on the interval of cows we have visited so far. At any point of our algorithm, we are extending an interval either by adding one cow to the left or one cow to the right, meaning that the minimum cost solution for any interval results in our location being either at the leftmost cow or the rightmost cow. This allows us to define our state: we keep track of the leftmost cow, the rightmost cow, and whether we are located at the left or the right of our interval. The state transition consists only of trying all possible ways to extend an interval by one cow (of which there are only 4). This can be seen in the solution below, which is O(N²) overall.

The following is a sample solution:

#include <cstdio>
#include <algorithm>
using namespace std;

FILE *fin = fopen ("cowrun.in", "r");
FILE *fout = fopen ("cowrun.out", "w");

const int MAXN = 1005;

int N;
int cows [MAXN];
int best [MAXN][MAXN][2];

int main ()
{
    memset (best, 63, sizeof (best));

    fscanf (fin, "%d", &N);

    for (int i = 1; i <= N; i++)
	fscanf (fin, "%d", cows + i);

    cows [++N] = 0;

    sort (cows + 1, cows + N + 1);

    for (int i = 1; i <= N; i++)
	if (cows [i] == 0)
	    best [i][1][0] = 0;


    for (int len = 1; len < N; len++)
    {
	int ccount = N - len;

	for (int i = 1; i + len <= N + 1; i++)
	{
	    best [i - 1][len + 1][0] <?= best [i][len][0] + ccount * (cows [i] -
cows [i - 1]);
	    best [i - 1][len + 1][0] <?= best [i][len][1] + ccount * (cows [i + len
- 1] - cows [i - 1]);

	    best [i][len + 1][1] <?= best [i][len][0] + ccount * (cows [i + len] -
cows [i]);
	    best [i][len + 1][1] <?= best [i][len][1] + ccount * (cows [i + len] -
cows [i + len - 1]);
	}
    }

    fprintf (fout, "%d\n", best [1][N][0] <? best [1][N][1]);

    return 0;
}

In addition, the memory of the solution can be reduced to O(N), as in the following solution:

#include <cstdio>
#include <algorithm>
using namespace std;

FILE *fin = fopen ("cowrun.in", "r");
FILE *fout = fopen ("cowrun.out", "w");

const int MAXN = 1005;

int N;
int cows [MAXN];
int best [MAXN][2], best2 [MAXN][2];

inline void mini (int &a, int b)
{
    if (b < a) a = b;
}

int main ()
{
    memset (best, 63, sizeof (best));

    fscanf (fin, "%d", &N);

    for (int i = 1; i <= N; i++)
	fscanf (fin, "%d", cows + i);

    cows [++N] = 0;

    sort (cows + 1, cows + N + 1);

    for (int i = 1; i <= N; i++)
	if (cows [i] == 0)
	    best [i][0] = 0;


    for (int len = 1; len < N; len++)
    {
	int ccount = N - len;

	memset (best2, 63, sizeof (best2));

	for (int i = 1; i + len <= N + 1; i++)
	{
	    mini (best2 [i - 1][0], best [i][0] + ccount * (cows [i] - cows [i - 1]));
	    mini (best2 [i - 1][0], best [i][1] + ccount * (cows [i + len - 1] - cows
[i - 1]));

	    mini (best2 [i][1], best [i][0] + ccount * (cows [i + len] - cows [i]));
	    mini (best2 [i][1], best [i][1] + ccount * (cows [i + len] - cows [i + len
- 1]));
	}

	memcpy (best, best2, sizeof (best));
    }

    fprintf (fout, "%d\n", best [1][0] <? best [1][1]);

    return 0;
}