| ||||||||||
| 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 | |||||||||
Re:单调队列O(L)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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator