搞死人的题目，注意本题的DP状态只与前一次状态相关，即可以用滚动数组记录状态，
其状态memo[i][j]表示这次（上次）的电脑（第x台）一直插到第j根插口时前x台的最小总耗费。
（另一种状态的记法是前i台占用到前j个插口，这样的时间和空间复杂度均为MN）。
优化方法应特别注意到任两根网线不会相交。
这样一来每台电脑独立情况下找到自己最适合的接口之后，在最优方案中只可能最多左移x个接口，或右移y个接口，x + y = n。
而通过将原来的M个接口去除不可能点（即确定每台电脑独立情况下找到自己最适合的接口之后，从左向右和从右向左分别迭代求出每台电脑可能的接口范围），将其标志为负，即可在DP时降低第二重循环的迭代次数。
另一个优化是在寻找每台电脑独立情况下找到自己最适合的接口时从两边同时进行，每次迭代都缩小查找范围的上下限。

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

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define MAXM 100000
#define MAXN 2000
#define INT_MAX 2000000000

class DPer
{
public:
	DPer(int m, int n);
	int operator () ();
	void Input();
protected:
	void InitNa();
	void CompressMS();
	int DP();
private:
	static int _memo[2][MAXM + 1];
	static int _nBegin[MAXN + 2];
	static int _nEnd[MAXN + 2];
	static int _ms[MAXM + 1];
	static int _ns[MAXN + 1];
	static int _na[MAXN + 1];
	int _m, _n;
};

int main()
{
	int m, n;
	scanf("%d %d", &m, &n);
	DPer dp(m, n);
	dp.Input();
	printf("%d\n", dp());
	return 0;
}

int DPer::_memo[2][MAXM + 1];
int DPer::_nBegin[MAXN + 2];
int DPer::_nEnd[MAXN + 2];
int DPer::_ms[MAXM + 1];
int DPer::_ns[MAXN + 1];
int DPer::_na[MAXN + 1];

DPer::DPer(int m, int n)
: _m(m), _n(n)
{
	if (*_memo)
	{
		memset(_memo, 0, sizeof(_memo));
	}
}

int DPer::DP()
{
	int i, j, cur, preBegin, preEnd;
	int end = _n + 1;
	for (i = 1, cur = 0, preBegin = 0, preEnd = 2; i < end; ++i, cur = 1 - cur)
	{
		int temp = INT_MAX;
		for (j = _nBegin[i]; j < _nEnd[i]; ++j)
		{
			int tempPreEnd = min(preEnd, j);
			tempPreEnd = max(tempPreEnd, preBegin + 1);	// 非常重要！如果没有则不能保证上一台电脑落在其可能插口范围之内。
			int tempSum = _memo[1 - cur][tempPreEnd - 1] + abs(_ns[i] - _ms[j]);
			if (tempSum < temp)
			{
				temp = tempSum;
			}
			_memo[cur][j] = temp;
		}
		preBegin = _nBegin[i];
		preEnd = _nEnd[i];		
	}
	return _memo[1 - cur][preEnd - 1];
}

// 每台电脑独立情况下找到自己最适合的接口
void DPer::InitNa()
{
	for (int nil = 1, nir = _n, l = 1, r = _m;
	nil <= nir; ++nil, --nir)
	{
		int tempR = r;
		while (l + 1 < r)
		{
			int mid = (l + r) >> 1;
			if (_ms[mid] >= _ns[nil]) 
			{
				r = mid;
			}
			else 
			{
				l = mid;
			}
		}
		int v1 = _ns[nil] - _ms[l];
		int v2 = _ms[r] - _ns[nil];
		_na[nil] = v1 < v2 ? l : r;
		int temp = _na[nil] + nil - _n;
		_nBegin[nil] = max(temp, 1);
		temp = _na[nil] + nil;
		_nEnd[nil] = min(temp, _m + 1);

		l = _na[nil];
		r = tempR;
		while (l + 1 < r)
		{
			int mid = (l + r) >> 1;
			if (_ms[mid] >= _ns[nir]) 
			{
				r = mid;
			}
			else 
			{
				l = mid;
			}
		}
		v1 = _ns[nir] - _ms[l];
		v2 = _ms[r] - _ns[nir];
		_na[nir] = v1 < v2 ? l : r;
		temp = _na[nir] + nir - _n;
		_nBegin[nir] = max(temp, 1);
		temp = _na[nir] + nir;
		_nEnd[nir] = min(temp, _m + 1);
		l = _na[nil];
		r = _na[nir];
	}
	_nEnd[_n + 1] = -1;
	_nBegin[0] = INT_MAX;
}

int DPer::operator () ()
{
	sort(_ns, _ns + _n + 1);
	sort(_ms, _ms + _m + 1);
	CompressMS();
	return DP();
}

// 剔除不可能的借口，确定每台电脑接口上下限
void DPer::CompressMS()
{
	InitNa();
	int i, j, k, pre, nt, end;
	for (i = 1, pre = 0, nt = 1; i < _n; ++i)
	{
		++pre;
		j = _na[i];
		end = _na[i + 1];
		if (j == end)
		{
			++pre;
			continue;
		}		
		while (j + 1 < end && pre)
		{
			++j;
			--pre;
		}
		k = j + 1;
		if (k < end)
		{
			while (_nEnd[nt] > k)
			{
				_nEnd[nt++] = k;
			}
		}
		for (; k < end; ++k)
		{
			_ms[k] = -_ms[k];
		}
	}
	for (i = _n, pre = 0, nt = _n; i > 1; --i)
	{
		++pre;
		j = _na[i];
		end = _na[i - 1];
		if (j == end)
		{
			++pre;
			continue;
		}
		while (_ms[j - 1] < 0 && pre)
		{
			--j;
			_ms[j] = -_ms[j];
			--pre;
		}
		while (pre && j - 1 > end)
		{
			--j;
			--pre;
		}
		if (j - 1 > end)
		{
			while (_nBegin[nt] < k)
			{
				_nBegin[nt--] = k;
			}
		}
	}
}

void DPer::Input()
{
	int i = 1;
	int end = _m + 1;
	for (; i < end; ++i)
	{
		scanf("%d", _ms + i);
	}
	end = _n + 1;
	for (i = 1; i < end; ++i)
	{
		scanf("%d", _ns + i);
	}
}

• 你跑这个数据好像错了吧？ (118) 20053565 2009-08-04 21:30:31