分析
此类问题似被统称为——最小区间覆盖问题。
首先考虑最简单的转移方程
表示覆盖[1,b[i]]的区间的最小代价。
考虑优化——快速找到区间最小值。只需要建立一棵线段树,每次查询对应区间,更新。代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") /* 区间最小覆盖问题 设f[x]覆盖[1,x]的最小花费,那么 把所有牛的上班时间按照右端点从大到 小排序,那么这个转移来自[s[i].l,s[i-1].r] */ #include<bits/stdc++.h> #define R register #define ll long long #define inf INT_MAX #define ls now<<1 #define rs ls|1 using namespace std; const int N=3e4+10,M=1e6+10; int n,en,tot; int f[N],k[M<<2]; struct nkl { int x,y; }s[N]; inline bool god(nkl xx,nkl yy) { return xx.y<yy.y; } inline void build(int now,int l,int r) { if(l==r) { k[now]=1e9; return ; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); k[now]=min(k[ls],k[rs]); } inline void add(int now,int l,int r,int x,int z) { if(l==r) { k[now]=min(k[now],z); return ; } int mid=(l+r)>>1; if(x<=mid) add(ls,l,mid,x,z); else add(rs,mid+1,r,x,z); k[now]=min(k[ls],k[rs]); } inline int find(int now,int l,int r,int x,int y) { if(x>y) return 1e9; if(l>=x&&r<=y) return k[now]; int mid=(l+r)>>1,ret=1e9; if(x<=mid) ret=find(ls,l,mid,x,y); if(mid<y) ret=min(ret,find(rs,mid+1,r,x,y)); return ret; } int main() { scanf("%d%d",&n,&en); for (int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y); sort(s+1,s+n+1,god); build(1,0,en);add(1,0,en,0,0); for (int i=1;i<=n;i++) { int l=max(s[i].x-1,0),r=min(en,s[i].y); int now=find(1,0,en,l,r); if(now>1e9) continue; add(1,0,en,r,now+1); } int ans=find(1,0,en,en,en); if(ans>1e8) puts("-1"); else printf("%d\n",ans); return 0; }