Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——定上下界的dp优化

Posted by fanhqme at 2009-12-12 08:44:22 on Problem 3375
首先,匹配/网络流/贪心是第一直觉,但可惜,貌似思路阻塞。

这时,就要使用dp了。
先看一个事实:如果computerA在computerB的右边,那么一定有一种最优方案,使
与A连接的插头在B的右边。
于是,得到dp思路:设f[i][j]表示前i个计算机已连接,第i台连接第j个接头的最
小代价。
f[i][j]=Min{f[i-1][k]|k<j}+i到j的距离
用一个变量记录前缀最小值,可以把复杂度降为O(MN)

剩下的就是优化。
一个事实:对于computerA,设他和第i个插头距离最近,那么在最优方案中,和A
连接的插头j和插头i的距离不会太大。
这个距离不会超过多少呢?
实践证明:-N<=i-j<=N
这样,可以忽略很多f[i][j],只考虑最优方案中可能用的的状态,复杂度降低为
O(N*N)

关键代码:
z=0;for (int i=0;i<M;i++)dp[i]=-1;
	for (int i=0;i<N;i++){
		bl=l;br=r;
		while (z<M-1 && B[z+1]<=A[i])z++;
		l=Max(0,z-N);r=Min(M-1,z+N);
		k=-1;
		if (i)for (int j=bl;j<l;j++)if (k==-1 || dp[j]<k && dp[j]!=-1)k=dp[j];
		if (i){
			for (int j=l;j<=r;j++){
				w=dp[j];
				if (k!=-1)dp[j]=k+Abs(B[j]-A[i]);
				else dp[j]=-1;
				if (k==-1 || k>w && w!=-1)k=w;
			}
		}else for (int j=l;j<=r;j++)dp[j]=Abs(B[j]-A[i]);
	}
	int ret;
	ret=-1;
	for (int i=l;i<=r;i++)if (ret==-1 || ret>dp[i] && dp[i]!=-1)ret=dp[i];

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator