传送门 很神的 D P DP DP题。首先要确定一个 D P DP DP的顺序保证答案的正确性。 对于两个元素，分四种情况讨论它们的关系： 如果 a i ⩽ b j a n d b i < a j a_i \leqslant b_j\ and\ b_i < a_j ai⩽bj and bi<aj，那么 i i i必须排在 j j j的前面。 如果 a i > b j a n d b i ⩾ a j a_i > b_j\ and\ b_i \geqslant a_j ai>bj and bi⩾aj，那么 j j j必须排在 i i i的前面。 如果 a i > b j a n d b i < a j a_i > b_j\ and\ b_i < a_j ai>bj and bi<aj，那么 i i i和 j j j相互不能更新。 如果 a i ⩽ b j a n d b i ⩾ a j a_i \leqslant b_j\ and\ b_i \geqslant a_j ai⩽bj and bi⩾aj，那么 i i i和 j j j相互可以更新。 对于后两种情况， i i i和 j j j的排列顺序是无所谓的，只需要保证前面两种的顺序是对的。 然而前面的两个比较关系并不满足严格弱序， s o r t sort sort会出问题。 考虑如何把这个大小关系转化： { a i ⩽ b j b i < a j ⟹ a i + b i < a j + b j \begin{cases} a_i \leqslant b_j \\ b_i < a_j \end{cases} \Longrightarrow a_i+b_i <a_j+b_j {ai⩽bjbi<aj⟹ai+bi<aj+bj 右式相当于是左式的一个必要条件，按照 a i + b i < a j + b j a_i+b_i <a_j+b_j ai+bi<aj+bj排序后，满足左边条件的数对一定会被排好序。
然后考虑一个转移的方程： f [ i ] [ j ] f[i][j] f[i][j]表示前 1 1 1~ i i i个元素中，选出元素的 a a a值为 j j j的最优方案。 考虑转移，为了方便描述，这里默认 a i ⩽ b i a_i \leqslant b_i ai⩽bi，其它情况判一下就行： f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j ] , j ∈ [ 1 , ∞ ) ) f[i][j]=max(f[i][j],f[i-1][j],j\in[1,\infty)) f[i][j]=max(f[i][j],f[i−1][j],j∈[1,∞))（不选第 i i i个） f [ i ] [ a [ i ] ] = m a x { f [ i ] [ a [ i ] ] , f [ i − 1 ] [ 1 f[i][a[i]]=max\{f[i][a[i]],f[i-1][1 f[i][a[i]]=max{f[i][a[i]],f[i−1][1~ a [ i ] ] } + c [ i ] a[i]]\}+c[i] a[i]]}+c[i]（选第 i i i个） f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j ] + c [ i ] ) , j ∈ ( a [ i ] , b [ i ] ] f[i][j]=max(f[i][j],f[i-1][j]+c[i]),j\in(a[i],b[i]] f[i][j]=max(f[i][j],f[i−1][j]+c[i]),j∈(a[i],b[i]]（选第 i i i个）
首先， i i i这一维可以压掉。 不选 a [ i ] a[i] a[i]相当于是直接继承过来。 第二个操作是区间查询最大值，单点修改。（要比较，取 m a x max max） 第三个操作是区间加，肯定比之前的大。所以其实并不用取 m a x max max。
于是就可以用线段树维护辣！！！ 由于 a a a的范围很大，所以离散化一下就行了。 注意单点改是取 m a x max max！因为有 b i < a i b_i<a_i bi<ai的情况！
#include<bits/stdc++.h> #define ll long long #define re register #define cs const cs int N=1e5+10; namespace IO{ cs int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;} template<typename T> inline T get(){ char ch=gc();T x=0; while(!isdigit(ch)) ch=gc(); while(isdigit(ch)) x=((x+(x<<2))<<1)+(ch^48),ch=gc(); return x; } inline int gi(){return get<int>();} inline ll gl(){return get<ll>();} } using IO::gi; using IO::gl; int n,st[N<<1],top=0,M; struct elements{ int a,b;ll c; friend inline bool operator<(cs elements &a,cs elements &b){return (a.a+a.b)<(b.a+b.b);} }P[N]; inline void disc(){ std::sort(st+1,st+top+1); M=std::unique(st+1,st+top+1)-(st+1); for(int re i=1;i<=n;++i) P[i].a=std::lower_bound(st+1,st+M+1,P[i].a)-st, P[i].b=std::lower_bound(st+1,st+M+1,P[i].b)-st; } #define lc (root<<1) #define rc (root<<1|1) #define mid (T[root].l+T[root].r>>1) inline ll max(ll x,ll y){return x>y?x:y;} inline void Max(ll &x,ll y){if(x<y)x=y;} inline int min(int x,int y){return x<y?x:y;} struct node{int l,r;ll mx,tag;}T[N<<3]; inline void pushup(int root){T[root].mx=max(T[lc].mx,T[rc].mx);} inline void pushnow(int root,ll val){T[root].tag+=val,T[root].mx+=val;} inline void pushdown(int root){ if(T[root].tag){ pushnow(lc,T[root].tag), pushnow(rc,T[root].tag), T[root].tag=0; } } inline void build(int root,int l,int r){ T[root].l=l,T[root].r=r; if(l==r){T[root].mx=T[root].tag=0;return;} build(lc,l,mid),build(rc,mid+1,r),pushup(root); } inline void update(int root,int pos,ll val){ if(T[root].l==T[root].r){Max(T[root].mx,val);return;} pushdown(root); (pos<=mid)?update(lc,pos,val):update(rc,pos,val);pushup(root); } inline void range_add(int root,int l,int r,ll val){ if(l<=T[root].l&&T[root].r<=r) return pushnow(root,val); pushdown(root); if(l> mid) return range_add(rc,l,r,val),pushup(root); if(r<=mid) return range_add(lc,l,r,val),pushup(root); return range_add(lc,l,mid,val),range_add(rc,mid+1,r,val),pushup(root); } inline ll querymax(int root,int l,int r){ if(l<=T[root].l&&T[root].r<=r) return T[root].mx; pushdown(root); if(l> mid) return querymax(rc,l,r); if(r<=mid) return querymax(lc,l,r); return max(querymax(lc,l,mid),querymax(rc,mid+1,r)); } int main(){ // freopen("pair.in","r",stdin); n=gi(); for(int re i=1;i<=n;++i) st[++top]=P[i].a=gi(),st[++top]=P[i].b=gi(),P[i].c=gl(); disc(),std::sort(P+1,P+n+1),build(1,1,M); for(int re i=1,A,B;i<=n;++i){ A=min(P[i].a,P[i].b),B=P[i].b; ll now=querymax(1,1,A);update(1,P[i].a,now+P[i].c); if(A+1<=B) range_add(1,A+1,B,P[i].c); }printf("%lld\n",T[1].mx); }