题目大意:给你很多条线段,开头结尾是$[l,r]$,让你覆盖整个区间$[1,T]$,求最少的线段数

题目传送门

线段树优化$DP$裸题..

先去掉所有能被其他线段包含的线段,这种线段一定不在最优解里

排序,让所有线段构成左右端点位置都递增的排列

定义$f[i]$表示第$i$条线段,覆盖到第$i$条线段右端点时,需要的最少的线段数

$f[i]=min(f[j]+1)\;(j<i,r[j]>=l[i])$

朴素是$n^2$转移的

开一棵最小值线段树,记录从$1$覆盖到位置$x$的最少线段数

每次求$f[i]$就是在线段树里区间查询。然后在$r[i]$位置更新即可

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 25010
#define M1 1000010
#define ll long long
#define dd double
#define inf 233333333
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
} struct SEG{
int mi[M1<<];
void pushup(int rt){ mi[rt]=min(mi[rt<<],mi[rt<<|]); }
void build(int l,int r,int rt)
{
mi[rt]=inf; if(l==r) return;
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
}
void update(int x,int l,int r,int rt,int w)
{
if(l==r){ mi[rt]=w; return; }
int mid=(l+r)>>;
if(x<=mid) update(x,l,mid,rt<<,w);
else update(x,mid+,r,rt<<|,w);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return mi[rt];
int mid=(l+r)>>,ans=inf;
if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<));
if(R>mid) ans=min(ans,query(L,R,mid+,r,rt<<|));
return ans;
}
}s; struct node{int l,r;}a[N1],tmp[N1];
int cmp(node s1,node s2){ if(s1.l!=s2.l) return s1.l<s2.l; return s1.r>s2.r; }
int n,m,nn;
int f[M1]; int main()
{
scanf("%d%d",&n,&m);
int i,ma,ans=inf;
for(i=;i<=n;i++) tmp[i].l=gint(),tmp[i].r=gint();
sort(tmp+,tmp+n+,cmp);
for(i=,ma=;i<=n;i++)
{
if(tmp[i].l>ma+){ puts("-1"); return ; }
if(tmp[i].r>ma) ma=tmp[i].r,a[++nn]=tmp[i];
}
s.build(,m,);
f[]=; s.update(a[].r,,m,,);
if(a[].r==m){ puts(""); return ; }
for(i=,ma=a[].r;i<=nn;i++)
{
f[i]=s.query(max(,a[i].l-),ma,,m,)+;
s.update(a[i].r,,m,,f[i]);
ma=a[i].r;
if(a[i].r==m) ans=f[i];
}
if(ans==inf) puts("-1");
else printf("%d\n",ans);
return ;
}
05-11 09:37
查看更多