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