uva 1474(dp)

题意：有n个队伍修路，有m个避难所，编号从1开始，给出了每个队伍和避难所的位置，每个队伍和避难所之间的距离是|a[i] - b[j]|，如果为每一个队伍分配避难所，且每个避难所至少被分配一个队伍，问每个队伍和自己的避难所之间最短距离和是多少，给出每个队伍分配的避难所编号。
题解：dp的状态很好找，因为距离差要最短，所以先把位置都排序，f[i][j]表示前i个队伍前j个避难所分配后的最短距离和。
f[i][j] = min(f[i - 1][j - 1]，f[i - 1][j]) + abs(a[i] - b[j])

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 4005;
const long long INF = 1e18;
struct Point {
    int v, id;
}p[N], s[N];
int n, m, path[N][N], res[N];
long long f[2][N];

bool cmp(Point a, Point b) {
    return a.v < b.v;
}

void print_path(int a, int b) {
    if (a == 0 || b == 0)
        return;
    res[p[a].id] = s[b].id;
    print_path(a - 1, b - path[a][b]);
}

int main() {
    while (scanf("%d", &n) == 1) {
        //input
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i].v);
            p[i].id = i;
        }
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d", &s[i].v);
            s[i].id = i;
        }
        //solve
        sort(p + 1, p + n + 1, cmp);
        sort(s + 1, s + m + 1, cmp);
        //dp
        for (int i = 1; i <= m; i++)
            f[0][i] = INF;
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            int now = i & 1;
            for (int j = 0; j <= m; j++)
                f[now][j] = INF;
            for (int j = 1; j <= m && j <= i; j++) {
                long long temp = abs(p[i].v - s[j].v);
                if (f[now ^ 1][j - 1] <= f[now ^ 1][j]) {
                    f[now][j] = f[now ^ 1][j - 1] + temp;
                    path[i][j] = 1;
                }
                else {
                    f[now][j] = f[now ^ 1][j] + temp;
                    path[i][j] = 0;
                }
            }
        }
        printf("%lld\n", f[n & 1][m]);
        //print path
        print_path(n, m);
        for (int i = 1; i < n; i++)
            printf("%d ", res[i]);
        printf("%d\n", res[n]);
    }
    return 0;
}