其实这道题不是很难，不难想到f[i]表示覆盖到[0,i]的最少喷头数
很明显是一个dp+单调队列的问题
但是细节问题比较多，首先是不能覆盖到[0,l]外面，所以长度为奇数不能被完全覆盖
还有一些区间[bi,ei]只能被一个喷头覆盖，这意味着[0,s],bi<s<ei也是不能被完全覆盖的
标记一下就好了
最后注意判断一下是否可行
const inf=;
type node=record
x,y:longint;
end;
var f,q:array[..] of longint;
can:array[..] of boolean;
a,b:array[..] of longint;
p,n,l,w,v,i,j,h,t,ans:longint; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure merge;
var l,r:longint;
begin
l:=a[];
r:=b[];
t:=;
for i:= to n do
begin
if a[i]<r then r:=max(r,b[i])
else begin
if r-l>v* then
begin
writeln(-);
halt;
end;
inc(t);
a[t]:=l;
b[t]:=r;
l:=a[i];
r:=b[i];
end;
end;
if r-l>v* then
begin
writeln(-);
halt;
end;
inc(t);
a[t]:=l;
b[t]:=r;
end; begin
readln(n,l);
readln(w,v);
for i:= to n do
readln(a[i],b[i]);
sort(,n);
merge;
for i:= to t do
for j:=a[i]+ to b[i]- do
can[j]:=true;
f[]:=;
h:=;
t:=;
for i:= to l do
begin
f[i]:=inf;
p:=i-*w;
if (p>=) then
begin
while (t>) and (h<t) and (f[q[t-]]>=f[p]) do dec(t);
if not can[p] then
begin
q[t]:=p;
inc(t);
end;
end;
if (can[i]) or (i mod =) then continue;
while (h<t) and (q[h]<i-*v) do inc(h);
if (h<t) then f[i]:=f[q[h]]+;
end;
if f[l]>=inf then writeln(-) else writeln(f[l]);
end.
const inf=;
type node=record
x,y:longint;
end;
var f,q:array[..] of longint;
can:array[..] of boolean;
a,b:array[..] of longint;
p,n,l,w,v,i,j,h,t,ans:longint; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure merge;
var l,r:longint;
begin
l:=a[];
r:=b[];
t:=;
for i:= to n do
begin
if a[i]<r then r:=max(r,b[i])
else begin
if r-l>v* then
begin
writeln(-);
halt;
end;
inc(t);
a[t]:=l;
b[t]:=r;
l:=a[i];
r:=b[i];
end;
end;
if r-l>v* then
begin
writeln(-);
halt;
end;
inc(t);
a[t]:=l;
b[t]:=r;
end; begin
readln(n,l);
readln(w,v);
for i:= to n do
readln(a[i],b[i]);
sort(,n);
merge;
for i:= to t do
for j:=a[i]+ to b[i]- do
can[j]:=true;
f[]:=;
h:=;
t:=;
for i:= to l do
begin
f[i]:=inf;
p:=i-*w;
if (p>=) then
begin
while (t>) and (h<t) and (f[q[t-]]>=f[p]) do dec(t);
if not can[p] then
begin
q[t]:=p;
inc(t);
end;
end;
if (can[i]) or (i mod =) then continue;
while (h<t) and (q[h]<i-*v) do inc(h);
if (h<t) then f[i]:=f[q[h]]+;
end;
if f[l]>=inf then writeln(-) else writeln(f[l]);
end.