Cow Checklist

The Problem Simplified

Given x green dots and y red dots, find the minimum energy spent visiting these dots given the requirement you have to visit the nth green dot before the n+1th green dot and the nth red dot before the n+1th red dot, but not necessarily consecutively. Assume the energy it takes to go from point a to point b is the square of their distance.

The Algorithm

Searching through all the (x+y)! (around) permutations seem very nasty. However, we realize that the energy to visit i green dots and j black and end at the last green dot ONLY depends on the energy to visit i-1 green dots and j black dots, ending at either the last green or red dot, whichever is optimal. The same applies for finding the required energy to end at the last red dot. This inspires a DP solution, in which we store two 2D arrays, one for ending at green dots and the other for red dots. The answer is in the first array for green dots. My code illustrates this method.

The Code

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

int dp[1001][1001][2]; // jp[i][j] = visit i alices j bobs, end at jth bob, start at 0th alice
struct dot
	int x, y;
	int dis(dot other)
		return (other.x - x)*(other.x - x) + (other.y - y)*(other.y - y);
	void operator=(dot other)
		x = other.x;
		y = other.y;
} hol[1001], gur[1001];

int main()
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &hol[i].x, &hol[i].y);
	for (int i = 0; i < m; i++)
		scanf("%d %d", &gur[i].x, &gur[i].y);
	memset(dp, 63, sizeof dp);
	for (int i = 0; i < 1001; i++)
		for (int j = 0; j < 1001; j++)
			for (int k = 0; k < 2; k++)
				if (k == 0 && i == 0) continue;
				if (k == 1 && j == 0) continue;
				dot source;
				if (k == 0) source = hol[i - 1];
				else source = gur[j - 1];
				if (i < n)
					dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + source.dis(hol[i]));
				if (j < m)
					dp[i][j + 1][1] = min(dp[i][j + 1][1], dp[i][j][k] + source.dis(gur[j]));