UVA 1474(dp + 推理)

Flatland government is building a new highway that will be used to transport weapons from its main weapon plant to the frontline in order to support the undergoing military operation against its neighbor country Edgeland. Highway is a straight line and there are n construction teams working at some points on it.

During last days the threat of a nuclear attack from Edgeland has significantly increased. Therefore the construction office has decided to develop an evacuation plan for the construction teams in case of a nuclear attack. There are m shelters located near the constructed highway. This evacuation plan must assign each team to a shelter that it should use in case of an attack.

Each shelter entrance must be securely locked from the inside to prevent any damage to the shelter itself. So, for each shelter there must be some team that goes to this shelter in case of an attack. The office must also supply fuel to each team, so that it can drive to its assigned shelter in case of an attack. The amount of fuel that is needed is proportional to the distance from the team's location to the assigned shelter. To minimize evacuation costs, the office would like to create a plan that minimizes the total fuel needed.

Your task is to help them develop such a plan.

Input

The input file contains several test cases, each of them as described below.

The first line of the input file contains n -- the number of construction teams (1n4000). The second line contains n integer numbers - the locations of the teams. Each team's location is a positive integer not exceeding 10⁹, all team locations are different.

The third line of the input file contains m -- the number of shelters (1mn).

The fourth line contains m integer numbers -- the locations of the shelters. Each shelter's location is a positive integer not exceeding 10⁹, all shelter locations are different.

The amount of fuel that needs to be supplied to a team at location x that goes to a shelter at location y is equal to | x - y|.

Output

For each test case, the output must follow the description below.

The first line of the output file must contain z -- the total amount of fuel needed. The second line must contain n integer numbers: for each team output the number of the shelter that it should be assigned to. Shelters are numbered from 1 to m in the order they are listed in the input file.

Sample Input

3 
1 2 3 
2 
2 10

Sample Output

8 
1 1 2

題意：一條公路上，n個施工隊，m個避難所，要求每個避難所至少一隊人，現在把施工隊分配給避難所，問避難時需要的最少移動總距離。

思路：dp[i][j]代表前i個施工隊放入前m個避難所，由於每個避難所至少一隊人，所以dp[i][j] = min(dp[i - 1][j - 1] + abs(a[i] - b[j]), dp[i - 1][j] + abs(min(a[i] - b[k]))。由於dp[i - 1][j] + abs(min(a[i] - b[k]),要找a和b之間距離最小的，時間復雜度會增加，但是其實如果把a,b都從小到大排序後，a[i]是肯定要放入b[j]的，可以證明，如果a[i] >= b[j]，a[i]到b[j]肯定最短，因為b[k < j] 小於b[j]。如果a[i] < b[j]的話，如果a[i]到b[k < j]的距離更短，那麼a[k < i]到它的距離肯定也更短，如果要用其他去b[j]，勢必會增加大於abs(b[j] - a[i])的距離，所以還是a[i]放入b[j]是最優的。

所以最後得出結論 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + abs(a[i] - b[j]); 然後這題數組直接開要4000*4000開不下，要用滾動數組去優化。

代碼：

#include 
#include 
#include 
#include 
using namespace std;
const long long INF = 1e17;
const int N = 4005;
int n, m, i, j, ans[N];
long long dp[2][N]; 
int path[N][N];
struct Q {
	int v, id;
} a[N], b[N];

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

void print(int n, int m) {
	if (n == 0 || m == 0) return;
	ans[a[n].id] = b[m].id;
	print(n - 1, m - path[n][m]);
}

long long solve() {
	for (i = 1; i <= m; i++)
		dp[0][i] = INF;
	dp[0][0] = 0;
	for (i = 1; i <= n; i++) {
		int now = i % 2;
		int pre = 1 - now;
		for (j = 0; j <= m; j++)
			dp[now][j] = INF;
		for (j = 1; j <= m && j <= i; j++) {
			if (dp[pre][j - 1] < dp[pre][j]) {
				dp[now][j] = dp[pre][j - 1] + abs(a[i].v - b[j].v);
				path[i][j] = 1;
			}
			else {
				dp[now][j] = dp[pre][j] + abs(a[i].v - b[j].v);
				path[i][j] = 0;
			}
		}
	}
	return dp[n%2][m];
}

int main() {
	while (~scanf("%d", &n)) {
		for (i = 1; i <= n; i++) {
			scanf("%d", &a[i].v);
			a[i].id = i;
		}
		scanf("%d", &m);
		for (i = 1; i <= m; i++) {
			scanf("%d", &b[i].v);
			b[i].id = i;
		}
		sort(a + 1, a + 1 + n, cmp);
		sort(b + 1, b + 1 + m, cmp);
		printf("%lld\n", solve());
		print(n, m);
		for (i = 1; i < n; i++)
			printf("%d ", ans[i]);
		printf("%d\n", ans[n]);
	}
	return 0;
}