uva 1474 - Evacuation Plan(dp)

題目連接：uva 1474 - Evacuation Plan

題目大意：給出n，表示有個施工隊，然後給出n個施工隊的位置；然後給出m，表示說有m個避難所，接著給出m個避難所得位置，現在要將每個施工隊分配給避難所，要求移動的總距離最小，並且沒有避難所空閒。

解題思路：dp[i][j]表示說i個施工隊使用j個避難所得最短距離，將施工隊和避難所的距離從小到大排序後，選取避難所就可以采取就近原則，path[i][j]用來記錄路徑，dp數組可以用滾動數組優化空間。

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int N = 4005;
const ll INF = 1e17;

struct team {
	int d, id;
} s[N], p[N];

int n, m, path[N][N], ans[N];
ll dp[2][N];

bool cmp(const team& a, const team& b) {
	if (a.d != b.d) return a.d < b.d;
	return a.id < b.id;
}

void init () {
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i].d);
		s[i].id = i;
	}

	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &p[i].d);
		p[i].id = i;
	}

	sort(s+1, s+n+1, cmp);
	sort(p+1, p+m+1, cmp);
}

ll solve () {
	for (int i = 1; i <= m; i++) dp[0][i] = INF;
	dp[0][0] = 0;
	
	for (int i = 1; i <= n; i++) {
		int u = i%2;
		int v = 1-u;
		for (int j = 0; j <= m; j++) dp[u][j] = INF;

		for (int j = 1; j <= m && j <= i; j++) {
			if (dp[v][j-1] < dp[v][j]) {
				dp[u][j] = dp[v][j-1] + abs(s[i].d - p[j].d);
				path[i][j] = 1;
			} else {
				dp[u][j] = dp[v][j] + abs(s[i].d - p[j].d);
				path[i][j] = 0;
			}
		}
	}
	return dp[n%2][m];
}

void put(int x, int y) {
	if (x == 0 || y == 0) return;
	ans[s[x].id] = p[y].id;
	put(x-1, y-path[x][y]);
}

int main () {
	while (scanf("%d", &n) == 1) {
		init ();
		printf("%lld\n", solve ());
		put(n, m);
		for (int i = 1; i < n; i++) printf("%d ", ans[i]);
		printf("%d\n", ans[n]);
	}
	return 0;
}