UVA 1474 Evacuation Plan

题意：有一条公路，上面有n个施工队，要躲进m个避难所中，每个避难所中至少有一个施工队，躲进避难所的花费为施工队与避难所的坐标差的绝对值，求最小花费及策略。

解法：将施工队和避难所按坐标排序，可以看出有下列递推关系，dp[i][j]表示前j个施工队进入前i个避难所的花费，则有dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1]) + |a[j] - b[i]|。由于每个避难所至少有一个施工队，所以j从i开始遍历。滚动数组优化。

用path记录当前施工队进入的是当前避难所还是下一个避难所。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
using namespace std;
int n, m;
struct node
{
int p, id;
bool operator < (const node& tmp) const
{
return p < tmp.p;
}
} a[4005], b[4005];
LL dp[2][4005];
int path[4005][4005];
int ans[4005];
int main()
{
while(~scanf("%d", &n))
{
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i].p);
a[i].id = i;
}
scanf("%d", &m);
for(int i = 1; i <= m; i++)
{
scanf("%d", &b[i].p);
b[i].id = i;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for(int i = 1; i <= n; i++)
dp[0][i] = LONG_LONG_MAX;
for(int i = 1; i <= m; i++)
{
dp[i & 1][i - 1] = LONG_LONG_MAX;
for(int j = i; j <= n; j++)
{
if(dp[(i + 1) & 1][j - 1] < dp[i & 1][j - 1])
{
dp[i & 1][j] = dp[(i + 1) & 1][j - 1] + abs(a[j].p - b[i].p);
path[i][j] = 1;
}
else
{
dp[i & 1][j] = dp[i & 1][j - 1] + abs(a[j].p - b[i].p);
path[i][j] = 0;
}
}
}
int prt = m;
for(int i = n; i > 0; i--)
{
ans[a[i].id] = b[prt].id;
prt -= path[prt][i];
}
printf("%lld\n", dp[m & 1][n]);
for(int i = 1; i <= n; i++)
{
if(i != 1)
printf(" ");
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}