A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
有很多細(xì)節(jié)不好考慮，應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過的。而且代碼寫的不好。將就看一下吧。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2000-9-10 14:03:51
File Name: pku3375.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxm = 100010;
int n, m;
int interface[maxm];
int computer[maxm];
int f[2][maxm];
int last[2];
int main()
{
while (scanf("%d%d", &m, &n) != EOF)
{
for (int i = 1; i <= m; i++)
scanf("%d", &interface[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &computer[i]);
sort(interface + 1, interface + 1 + m);
sort(computer + 1, computer + 1 + n);
for (int i = 0; i <= m; i++)
f[1][i] = maxint;
for (int i = 0; i <= m; i++)
f[0][i] = 0;
last[0] = 0;
for (int i = 1; i <= n; i++)
{
int l = 1;
int r = m;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (interface[mid] >= computer[i])
r = mid;
else
l = mid;
}
int st = max(l - n - 1, 1);
int ed = min(l + n + 1, m);
int now = i % 2;
int prev = (i + 1) % 2;
last[now] = ed;
for (int j = st; j <= ed; j++)
{
if (f[prev][j - 1] != maxint)
f[now][j] <?= f[prev][j - 1] + abs(computer[i] - interface[j]);
else if (last[prev] < j - 1)
f[now][j] <?= f[prev][last[prev]] + abs(computer[i] - interface[j]);
f[now][j] <?= f[now][j - 1];
}
for (int j = 0; j <= m; j++)
f[prev][j] = maxint;
}
int ans = maxint;
for (int i = 0; i <= m; i++)
ans <?= f[n % 2][i];
printf("%d\n", ans);
}
return 0;
}