uva 1474 - Evacuation Plan(dp)

제목 연결: uva 1474 - Evacuation Plan
제목의 대의: n을 제시하면 시공팀이 있다는 것을 표시하고 n개의 시공팀의 위치를 제시한다.그리고 m을 제시하면 m개의 피난처가 있다고 한다. 이어서 m개의 피난처 소득 위치를 제시한다. 지금은 각 시공팀을 피난처에 분배해야 한다. 이동의 총 거리가 가장 작고 피난처가 비어 있지 않다고 요구한다.
문제풀이 사고방식: dp[i][j]는 i개 시공팀이 j개의 피난으로 얻은 가장 짧은 거리를 사용하고 시공팀과 피난소의 거리를 작은 것에서 큰 것으로 정렬한 후에 피난소를 선택하면 근접 원칙을 취할 수 있다고 말한다. path[i][j]는 경로를 기록하는데 dp수조는 롤러수조로 공간을 최적화할 수 있다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

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
", solve ());
		put(n, m);
		for (int i = 1; i < n; i++) printf("%d ", ans[i]);
		printf("%d
", ans[n]);
	}
	return 0;
}