#P1545. [USACO04DEC] Dividing the Path G

    ID: 8317 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划,dp2004线段树USACO单调队列动态规划优化

[USACO04DEC] Dividing the Path G

题目描述

约翰的奶牛们发现山脊上的草特别美味。为了维持草的生长,约翰打算安装若干喷灌器。

为简化问题,山脊可以看成一维的数轴,长为 L (1L106)L\ (1\le L\le 10^6),而且 LL 一定是一个偶数。每个喷灌器可以双向喷灌,并有确定的射程,该射程不短于 AA,不长于 BBAAB(1AB103)B(1\le A\le B\le 10^3) 都是给出的正整数。它所在位置的两边射程内,都属它的灌溉区域。

现要求山脊的每一个区域都被灌溉到,而且喷灌器的灌溉区域不允许重叠。约翰有 N(1N103)N(1\le N\le 10^3) 只奶牛,每一只都有特别喜爱的草区,第 ii 奶牛的草区是 [Si,Ei][S_i,E_i],不同奶牛的草区可以重叠。现要求,每只奶牛的草区仅被一个喷灌器灌溉。

注意:

  1. 数轴 LL00 开始标记(即坐标范围 0L0\sim L
  2. 喷灌器坐标和射程必须为整数,对于坐标为 ii 射程为 xx 的喷灌器,它的灌溉范围为 [ix,i+x][i-x,i+x]
  3. 浇灌区间必须在山脊范围内。例如,不能在 00 位置放一个半径为 11 的浇灌器。

寻找最少需要的喷灌器数目。

输入格式

第一行两个整数 N,LN,L

第二行两个整数 A,BA,B

然后 NN 行每一行两个整数 Si,EiS_i,E_i1Si<EiL1\le S_i < E_i\le L)。

输出格式

一行,输出所需的最少洒水器数量。如果无法为农夫约翰设计喷头配置,则输出 1-1

2 8
1 2
6 7
3 6
3

提示

对于 100%100\% 的数据,1L1061\le L\le 10^61A,B1031\le A,B\le 10^31N1031\le N\le 10^31Si<EiL1\le S_i<E_i\le L

样例解释: