Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
雁过留声——定上下界的dp优化首先,匹配/网络流/贪心是第一直觉,但可惜,貌似思路阻塞。 这时,就要使用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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator