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

Re:单调队列O(L)

Posted by lr_bob at 2012-04-18 12:57:20 on Problem 2373
In Reply To:单调队列O(L) Posted by:Stareven at 2010-12-26 10:54:43
> 又是单调队列。。。
> 首先容易想到将Segment合并,得到两两不相交的Segment。将Segment排序后就很好处理了。
> 定义f[i]表示覆盖到第i个点时所能需要用的数目。那么
> f[i]=min{f[j]}+1  (2A<=i-j<=2B)
> or
> f[i]=INF  (该点被某Segment覆盖)
> 其中F[i]=INF的情况看个人如何处理了。我的做法是开一个int s,表示当执行到i时,第一个右端点大于i的segment的下标,然后判断i是否在此Segment内就行。
> 而第一种情况,自然想到单调队列。需要注意的是,加入队列的f[k]有延迟性,这决定于A。所以每次运行到i这个位置是,将f[i-2A]的插入队列即可。

大牛,能把延迟性那部分详细的说一下么?不方便的话留个qq也好,不太懂你的意思

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