又是单调队列。。。
首先容易想到将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]的插入队列即可。

• Re:单调队列O(L) (376) lr_bob 2012-04-18 12:57:20
• Re:单调队列O(L) (376) lr_bob 2012-04-18 12:58:05
• Re:单调队列O(L) (376) lr_bob 2012-04-18 13:00:18