4 条题解

  • 0
    @ 2024-11-22 21:36:05
    #include<bits/stdc++.h>
    #define mst(a,b) memset(a,b,sizeof a)
    template<class T>inline void read(T &x){x=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';x=f?(~(x-1)):x;}
    template<class T>inline void write(T x){if(x<0)return putchar('-'),write(-x),void();if(x>=10)write(x/10);putchar(x%10+'0');return;}
    template<class T>inline void print(T x){write(x);putchar('\n');}
    template<typename type,typename ...T>inline void read(type &x,T&...y){read(x),read(y...);}
    using namespace std;
    const int N=5e3,M=1e5;
    int n,m;
    struct node{
    	int l,r,v;
    	inline friend bool operator <(node _x,node _y){
    		return _x.r<_y.r;
    	}
    }wt[N];
    int dp[M];
    signed main(){
    	read(n,m);
    	for(int i=1;i<=n;++i){
    		read(wt[i].l,wt[i].r,wt[i].v);
    	}
    	sort(wt+1,wt+n+1);
    	mst(dp,0);
    	for(int i=1,j=1;i<=m;++i){
    		dp[i]=dp[i-1];
    		for(;j<=n&&wt[j].r<=i;++j){
    			dp[wt[j].r]=max(dp[wt[j].r],dp[wt[j].l-1]+wt[j].v);
    		}
    	}
    	print(dp[m]);
    	return 0;
    }
    

    信息

    ID
    952
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    87
    已通过
    17
    上传者