poj3375 Network Connection

Description

There are (M) network interfaces in the wall of aisle of library. And (N) computers next to the wall need to be connected to the network. A network interface can only connect with one computer at most. To connect an interface with coordinate (x) with a computer with coordinate (y) needs (|x - y|) unit of length of network cable. Your task is to minimize the total length of network cables to be used.

Input

The first line contains two integers (M (1 ≤ M ≤ 100000), N (1 ≤ N ≤ 2000, N ≤ M)). The following (M + N) lines each contains a integer coordinate. The first (M) coordinates are corresponding to the network interfaces, and the next (N) ones corresponding to the computers. All coordinates are arranged in ([0, 1000000]). Distinct interfaces may have the same coordinate, so do the computers.

Output

Print an integer, representing minimum length of network cables to be used.

Sample Input

4 2
1
10
12
20
11
15

Sample Output

4

排序+离散化。
状态(f[i][j])表示考虑前(i)台电脑，最后一台插在第(j)个接口上的最小代价。转移$$f[i][j] = min_{i-1 le k < j} { f[i-1][k]+mid A_i-B_j mid }$$可用前缀和优化，复杂度(O(NM))。
减少无用状态：每台电脑的接口一定不会离他很远。假设离(i)最近的接口为(j)，只需要枚举(j-N sim j+N)这些接口即可，这里面一定有些是空的。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;

typedef long long ll;
const int maxn = 2010,maxm = 100010;
const ll inf = 1LL<<60;
ll f[2][maxm],ans = inf; int N,M,A[maxm],B[maxn];

inline int gi()
{
	char ch; int ret = 0,f = 1;
	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
	if (ch == '-') f = -1,ch = getchar();
	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
	return ret*f;
}

int main()
{
	freopen("3375.in","r",stdin);
	freopen("3375.out","w",stdout);
	M = gi(); N = gi();
	for (int i = 1;i <= M;++i) A[i] = gi();
	for (int i = 1;i <= N;++i) B[i] = gi();
	sort(A+1,A+M+1); sort(B+1,B+N+1);
	for (int i = 0;i <= M;++i) f[1][i] = inf;
	for (int i = 1,now = 1,last = 0,Lastl = 0,Lastr = M;i <= N;++i,swap(now,last))
	{
		int pos = lower_bound(A+1,A+M+1,B[i])-A,l = max(1,pos-N-1),r = min(M,pos+N+1);
		for (int j = l;j <= r;++j) f[now][j] = min(f[now][j-1],f[last][min(j-1,Lastr)]+(ll)abs(A[j]-B[i]));
		for (int j = Lastl;j <= Lastr;++j) f[last][j] = inf;
		Lastl = l; Lastr = r;
	}
	for (int i = 1,now = N&1;i <= M;++i) ans = min(ans,f[now][i]);
	cout << ans << endl;
	fclose(stdin); fclose(stdout);
	return 0;
}