线段树优化dp 20pts求条
查看原帖
线段树优化dp 20pts求条
639198
Steve_xh楼主2024/12/18 16:52
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int MAXN=100005,mod=998244353,inf=0x3f3f3f3f3f3f3f3fll;
int n,st,en;
struct Cow{
    int l,r,c;
    Cow(){}
    friend istream& operator>>(istream& is,Cow& o){is>>o.l>>o.r>>o.c;++o.l,++o.r;return is;}
    bool operator<(const Cow& o) const{
        if(r==o.r){
            if(l==o.l)
                return c<o.c;
            return l<o.l;
        }
        return r<o.r;
    }
}a[MAXN];
int f[MAXN];
struct SegTree{
    int l,r,v;
    int tag;
}t[MAXN<<2];
inline void pushup(int x){
    t[x].v=min(t[x<<1].v,t[x<<1|1].v);
}
inline void addtag(int x,int w){
    if(!~t[x].tag)
        t[x].tag=w;
    else
        t[x].tag=min(t[x].tag,w);
    t[x].v=min(t[x].v,w);
}
inline void pushdown(int x){
    if(!~t[x].tag)
        return ;
    addtag(x<<1,t[x].tag);
    addtag(x<<1|1,t[x].tag);
    t[x].tag=-1;
}
void bt(int x,int l,int r){
    t[x].l=l,t[x].r=r;
    t[x].tag=-1;
    if(l==r)
        return (void)(t[x].v=inf);
    int mid=(l+r)>>1;
    bt(x<<1,l,mid);
    bt(x<<1|1,mid+1,r);
}
int query(int x,int l,int r){
    if(l>r)
        return 0;
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].v;
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1,ans=inf;
    if(l<=mid)
        ans=min(ans,query(x<<1,l,r));
    if(mid<r)
        ans=min(ans,query(x<<1|1,l,r));
    return ans;
}
void upd(int x,int l,int r,int w){
    if(l>r)
        return ;
    if(l<=t[x].l&&t[x].r<=r)
        return addtag(x,w);
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid)
        upd(x<<1,l,r,w);
    if(mid<r)
        upd(x<<1|1,l,r,w);
    pushup(x);
}
int ans=-1;
signed main(){
    // freopen("P4644_1.in","r",stdin);
    // freopen("P4644.out","w",stdout);
    memset(f,inf,sizeof(f));
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>st>>en;
    ++st,++en;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    bt(1,1,en);
    upd(1,1,st-1,0);
    f[st]=0;
    for(int i=1;i<=n;i++){
        if(a[i].r<st)
            continue;
        if(a[i].l<=st)
            f[a[i].r]=min(f[a[i].r],a[i].c);
        else
            f[a[i].r]=min(f[a[i].r],query(1,a[i].l-1,a[i].r-1)+a[i].c);
        upd(1,a[i].r,a[i].r,f[a[i].r]);
    }
    if(f[en]==inf)
        cout<<-1;
    else
        cout<<f[en];
    

    // cerr<<'\n';
    // for(int i=1;i<=en;i++)
    //     cerr<<f[i]<<" ";
    // cerr<<'\n';
    // for(int i=1;i<=n;i++)
    //     cerr<<a[i].l<<" "<<a[i].r<<" "<<a[i].c<<'\n';
    return 0;
}

孩子好不容易第一次一眼秒式子,救救孩子吧。

2024/12/18 16:52
加载中...