题目连接：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; }