1 条题解

  • 0
    @ 2023-8-25 16:04:34
    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #define ll long long
    using namespace std;
    const int INF=0x3f3f3f3f,MAXX=100000;
    int delta=10;
    int n,l,r;
    int cnt;
    int dp[MAXX+5];
    struct tree{int l,r,minn;}tree[MAXX*8+5];
    struct node{int l,r,v;}t[MAXX+5];
    bool cmp(node x,node y){return x.r<y.r;}
    void Build(int k,int l,int r)
    {
        tree[k].l=l;tree[k].r=r;tree[k].minn=INF;
        if(l==r){return;}
        int mid=(l+r)>>1;
        Build(k<<1,l,mid);
        Build(k<<1|1,mid+1,r);
    }
    void add(int k,int x,int v)
    {
        if(x<tree[k].l||x>tree[k].r)return;
        tree[k].minn=min(tree[k].minn,v);
        int mid=(tree[k].l+tree[k].r)>>1;
        add(k<<1,x,v);add(k<<1|1,x,v);
    }
    int ask(int k,int l,int r)
    {
        int ans=INF;
        if(l<=tree[k].l&&r>=tree[k].r)return tree[k].minn;
        int mid=(tree[k].l+tree[k].r)>>1;
        if(l<=mid)ans=min(ans,ask(k<<1,l,r));
        if(r>mid)ans=min(ans,ask(k<<1|1,l,r));
        return ans;
    }
    int main()
    {
        Build(1,1,100000);
        scanf("%d %d %d",&n,&l,&r);
        l+=10;r+=10;
        for(int i=1;i<=n;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            x+=10;y+=10;
            if(x<l)x=l;if(y>r)y=r;
            if(x>y)continue;
            t[++cnt].l=x;t[cnt].r=y;t[cnt].v=z;
        }
        sort(t+1,t+cnt+1,cmp);
        memset(dp,0x3f,sizeof(dp));
        dp[l]=0;
        add(1,l,0);
        for(int i=1;i<=cnt;i++)
        {
            int k=INF;
            k=min(k,ask(1,t[i].l-1,t[i].r));
            dp[t[i].r]=min(dp[t[i].r],k+t[i].v);
            add(1,t[i].r,dp[t[i].r]);
        }
        if(dp[r]==INF)printf("-1");
        else printf("%d",dp[r]);
        return 0;
    }
    
    • 1

    [Usaco2005 Dec]Cleaning Shifts 清理牛棚

    信息

    ID
    1672
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    3
    上传者