《算法竞赛进阶指南》0x58数据结构优化DP AcWing298 DP解决最少区间数覆盖

题目链接：https://www.acwing.com/problem/content/297/

给定区间长度，和n个区间，问最少多少个区间能够覆盖[1,m]长度的区间。

dp状态：到i位置覆盖了[1,i]需要的最少区间数量，转移方程是：先找所有右端点是i的区间，其左右端点分别是l,r,那么f[l-1~r-1]的最小值+1就是最终的结果。通过线段树维护这个f数组可以在O(logm)时间内完成查询以及插入一个值f[i]，注意区间是从[0,m]的，最初有f[0]=0,其余都是inf。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 25010,T=1000010,inf=1e8;
int n,m;
struct Range{
    int l, r;
    bool operator < (const Range& b)const {
        return r<b.r;
    }
}range[N];
struct node{
    int l,r,v;
}t[T<<2];

void pushup(int rt){
    t[rt].v=min(t[rt<<1].v,t[rt<<1|1].v);
}
void build(int rt,int l,int r){
    t[rt]={l,r,inf};
    if(l==r)return;
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
int query(int rt,int L,int R){
    if(t[rt].l>=L && t[rt].r<=R)return t[rt].v;
    int mid=t[rt].l+t[rt].r>>1;
    int res=inf;
    if(L<=mid)res=min(res,query(rt<<1,L,R));
    if(R>mid)res=min(res,query(rt<<1|1,L,R));
    return res;
}
void update(int rt,int pos,int C){
    if(t[rt].l==t[rt].r){
        t[rt].v=min(t[rt].v,C);
        return;
    }
    int mid=t[rt].l+t[rt].r>>1;
    if(pos<=mid)update(rt<<1,pos,C);
    else update(rt<<1|1,pos,C);
    pushup(rt);
}

int main(){
    cin>>n>>m;//区间数量以及区间长度 
    for(int i=1;i<=n;i++)scanf("%d%d",&range[i].l,&range[i].r);
    sort(range+1,range+n+1);

    build(1,0,m);//最初的时候f[0]=0
    update(1,0,0);
    for(int i=1;i<=n;i++){
        int l=range[i].l,r=range[i].r;
        int v=query(1,l-1,r-1)+1;
        update(1,r,v);
    } 
    int res=query(1,m,m);
    if(res==inf)res=-1;
    cout<<res<<endl;
    
    return 0;
}

《算法竞赛进阶指南》0x58数据结构优化DP AcWing298 DP解决最少区间数覆盖

相关推荐