题目描述
约翰的奶牛们发现山脊上的草特别美味。为了维持草的生长，约翰打算安装若干喷灌器。
为简化问题，山脊可以看成一维的数轴，长为L(1≤L≤1,000,000)L(1≤L≤1,000,000)，而且L一定是一个偶数。每个喷灌器可以双向喷灌，并有确定的射程，该射程是一个整数，且不短于AA，不长于BB。A,B(1≤A≤B≤1000)A,B(1≤A≤B≤1000)都是给出的正整数。它所在位置的两边射程内，都属它的灌溉区域。现要求山脊的每一个区域都被灌溉到，而且喷灌器的灌溉区域不允许重叠。
约翰有N(1≤N≤1000)N(1≤N≤1000)只奶牛，每一只都有特别喜爱的草区，第i只奶牛的草区是[Si，Ei][Si，Ei]，不同奶牛的草区可以重叠。现要求，每只奶牛的草区仅被一个喷灌器灌溉。寻找最少需要的喷灌器数目。
输入数据
第11行：N,LN,L.
第22：A,BA,B.
第33到N+2N+2行：每行22个整数Si,Ei,0≤S<E≤LSi,Ei,0≤S<E≤L.
输出数据
最小的喷灌器数目。如果无法设计出满足条件的喷灌器数目，请输出−1−1.
样例输入
2 8
1 2
6 7
3 6样例输出
3
`样例说明
如下图，只需安装三个喷灌器。c1,c2c1,c2为奶牛们的草区。
|-----c2----|-c1|
|---1---|-------2-------|---3---|
+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8数据范围
对于30%30%的数据，L≤100L≤100。
对于60%60%的数据，L≤10000L≤10000。
对于100%100%的数据，1≤L≤1,000,000，1≤A≤B≤1000，1≤N≤10001≤L≤1,000,000，1≤A≤B≤1000，1≤N≤1000。
题目分析
这道题我觉得我这辈子都AC不了了，其实就是在deque上面跑一遍单调就可以了。
好吧我其实AC了，代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1999999999
int n,l,a,b,f[];
bitset<>vis;
deque<int> q;
signed main(){
freopen("divide.in","r",stdin),freopen("divide.out","w",stdout);
cin>>n>>l>>a>>b;
for (int i=,s,e;i<=n;++i) {
cin>>s>>e;
for (int j=s+;j<e;++j) vis[j]=;
}for (int i=; i<=l; ++i) {
f[i]=inf;
while(!q.empty()&&q.front()<i-*b) q.pop_front();
if(!vis[i]&&i%==&&!q.empty())
f[i]=min(f[i],f[q.front()]+);
if(i-*a+>=&&!vis[i-*a+]&&(i-*a+)%==){
while(!q.empty()&&f[i-*a+]<f[q.back()]) q.pop_back();
q.push_back(i-*a+);
}}if (f[l]!=inf) cout<<f[l];
else cout<<-;
return ;
}
代码说明
不知道说什么好，过几次我讲一讲我和她的故事。