poj2373专题

poj2373 Dividing the Path 单调队列dp

题意:在长为L的草地上装喷水头,喷射是以这个喷水头为中心,喷水头的喷洒半径是可调节的,调节范围为[a,b]。要求草地的每个 点被且只被一个喷水头覆盖,并且有些连续区间必须被某一个喷水头覆盖,而不能由多个喷头分段完全覆盖,求喷水头的最小数目。 思路:设dp[i]表示正好喷到i这个位置缩安放的最少喷泉数,那么dp[i]=min(dp[k])+1  (i - 2 * B  <=  k <=  i -