POJ 2376 Cleaning Shifts (线段树优化DP)

题目大意：给你很多条线段，开头结尾是$[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 ;

 }

巴特西

POJ 2376 Cleaning Shifts (线段树优化DP)

最新文章

热门文章