4 条题解
-
0
#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
- 上传者