DP/单调队列优化
首先不考虑奶牛的喜欢区间，dp方程当然是比较显然的：$ f[i]=min(f[k])+1,i-2*b \leq k \leq i-2*a $ 当然这里的$i$和$k$都是偶数啦~这个应该很好理解吧……每次喷灌的都是一个偶数长度的区间嘛……
那么加上奶牛的喜欢区间的话，只需这样：当$ i>cow[j].x $时，令$ i=cow[j].y , j++$ 也就是说中间的位置全部不考虑放喷灌器。
显然我们对于每个节点的 k 是可以用单调队列维护的！嗯看到这里的同学可以先自己试着去写写看啦~
如果过了样例不要着急，来试试我这组数据：
Trick：
每个奶牛的喜欢区间是一个【开区间】！分界点是可以被不同的喷灌器灌溉的（仔细看看样例的图）
一开始英文题面嘛……看了中文没细看英文……没看到还有【不合法情况输出-1】so sad……
每个f[i]不能刚算出来就弹队尾+进队尾，因为此时下一个位置为 i+2 ，可能会把能够转移到i+2的合法状态弹出去，而f[i]是不能转移到f[i+2]的！（因为有a的限制）所以会造成f[i+2]计算错误（当然f[l]就也有可能出错了。
事实上由于我们维护的队列是一个合法状态区间，所以目前不合法的状态不应该进队，而是应该在每次更新f[i]之前让 f[i-2*a] 进队，这样可以保证队列中所有节点都为合法状态。
然而！！刚才那种做法会有漏洞！因为我们会在遇到奶牛的喜欢区间的时候跳！过！去！所以一些合法状态就会来不及进队（比如我给的数据中的f[6]……所以在遇到奶牛区间的时候要将这个区间内所有合法的状态进队（当然要维护队列单调性了……需要弹队尾）
/**************************************************************
Problem: 1986
User: Tunix
Language: C++
Result: Accepted
Time:40 ms
Memory:9092 kb
****************************************************************/ //POJ 2373
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*=sign;
}
const int N=1e6+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
//#define debug
struct Cow{
int x,y;
Cow(){}
bool operator < (const Cow &b)const{
return x<b.x || (x==b.x && y<b.y);
}
}cow[];
int f[N],n,l,a,b;
int q[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("2373.in","r",stdin);
// freopen("2373.out","w",stdout);
#endif
n=getint(); l=getint(); a=getint(); b=getint();
F(i,,n) cow[i].x=getint(),cow[i].y=getint();
sort(cow+,cow+n+);
#ifdef debug
F(i,,n) printf("%d %d\n",cow[i].x,cow[i].y);
cout <<endl;
#endif
int j=;
F(i,,l) f[i]=INF;
int st=,ed=;
f[]=;
q[ed++]=;
for(int i=;i<=l;i+=){
while(i>cow[j].x && j<=n){
int last=i;
i=max(i,(cow[j].y+)/*),j++;
for(int I=last;I<=i;I+=)
if (f[I-*a]!=INF){
while(st<ed && f[q[ed-]]>f[I-*a]) ed--;
q[ed++]=I-*a;
}
}
while(st<ed && q[st]<i-*b) st++;
if(f[i-*a]!=INF){
while(st<ed && f[q[ed-]]>f[i-*a]) ed--;
q[ed++]=i-*a;
}
if (st<ed && i-q[st]>=*a) f[i]=f[q[st]]+;
}
#ifdef debug
F(i,,l) printf("%d ",f[i]==INF ? - : f[i]);
cout <<endl;
#endif
printf("%d\n",f[l]==INF ? - : f[l]);
return ;
}