题目地址：http://poj.org/problem?id=2373
从线段的起点向终点安装喷水头，令f(X)表示：所安装喷水头的喷洒范围
恰好覆盖直线上的区间[0 X]时，最少需要多少个喷水头
显然，X应满足下列条件
X为偶数
X所在位置不会出现奶牛，即X不属于任何一个(S,E)
X>=2A
当X>2B时，存在Y∈[X-2B，X-2A]且Y满足上述三个条件，使得
f(X)=f(Y)+1
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000+5;
const int INF=(1<<30);
typedef pair<int,int> pii;
int d[maxn],N,L,cowThere[maxn],A,B;
// d(x) 0~x处最少几个浇水装置
int solve()
{A<<=1;B<<=1;priority_queue<pii,vector<pii>,greater<pii> > pq; //(fx,x)for(int i=A;i<=B;i+=2) if(!cowThere[i]){d[i]=1;if(i<=B+2-A) pq.push(pii(1,i));}for(int x=B+2;x<=L;x+=2) //X只与[X-2B,X-2A]有关 {if(!cowThere[x]){while(!pq.empty()){if(pq.top().second<x-B) pq.pop();else break;}if(!pq.empty()) d[x]=pq.top().first+1;}if(d[x+2-A]!=INF) pq.push(pii(d[x+2-A],x+2-A)); }return d[L];
}
int main()
{cin>>N>>L>>A>>B;memset(cowThere,0,sizeof(cowThere)); for(int i=0;i<N;i++) {int S,E;cin>>S>>E;cowThere[S+1]++; //S点可以放 cowThere[E]--; //E点也可以 }int cow=0;for(int i=0;i<=L;i++){d[i]=INF;cow+=cowThere[i];cowThere[i]=cow>0;}int ans=solve();cout<<(ans==INF?-1:ans)<<endl;return 0;
}