Link
Solution
容易想到用 (f_i) 表示顶部圆环是 (i) 时的塔的最大高度。考虑如何转移，一个圆环 (i) 能放在另一个圆环 (j) 上，必有 (b_ileq b_j)，所以容易想到按照 (b) 降序排序，那么 (f_i) 只需要从 (j (j<i)) 转移，就没有后效性。容易写出转移方程
[f_i=max limits_{a_j<b_i} {f_j}+h_i quad jin[1,i)
]
形象地说就是在前 (i-1) 个圆环中，找到 (a) 值小于一个值的所有 (f) 的最大值。显然可以离散化 (a) 和 (b) 后用树状数组维护。
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100007
#define ll long long
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
struct Node{
int a,b; ll h;
bool operator <(const Node &x) const{
return b!=x.b? b>x.b:a>x.a;
}
}t[N];
int n,X[N<<1],sz;
ll f[N],c[N<<1];
inline int lowbit(int x){return -x&x;}
inline void add(int x,ll v){while(x<=sz)c[x]=max(c[x],v),x+=lowbit(x);}
inline ll query(int x){ll ret=0;while(x)ret=max(ret,c[x]),x-=lowbit(x);return ret;}
int main(){
n=read();
for(int i=1;i<=n;i++){
t[i].a=read(),t[i].b=read(),t[i].h=read();
X[(i<<1)-1]=t[i].a,X[i<<1]=t[i].b;
}
sort(t+1,t+1+n),sort(X+1,X+1+2*n);
sz=unique(X+1,X+1+2*n)-(X+1);
for(int i=1;i<=n;i++){
t[i].a=lower_bound(X+1,X+1+sz,t[i].a)-X;
t[i].b=lower_bound(X+1,X+1+sz,t[i].b)-X;
}
ll ans=0;
for(int i=1;i<=n;i++){
f[i]=query(t[i].b-1)+t[i].h;
add(t[i].a,f[i]);
ans=max(ans,f[i]);
}
printf("%lld",ans);
}
后面发现并不需要树状数组，观察这句话：
f[i]=query(t[i].b-1)+t[i].h;
因为 (b) 是单调不增的，所以决策集合一直在减小。对于三个圆环 (j) 、(i) 和 (k)，且有 (j<i<k)，如果 (i) 不能从 (j) 转移过来，那么 (k) 也一定不能从 (j) 转移。所以我们可以维护这个决策集合，如果 (j) 不合法就直接删掉而不会对后面造成影响。再次观察转移方程，每次我们取了决策集合里面的最大值，之后又加上了一个正整数 (h)，所以再把现在更新出来的 (f_i) 加入决策集合，(f_i) 就会成为决策集合里面的最大值，所以决策集合里的 (f) 也具有单调性，且是单增的。那么剩下的就可以用单调栈来维护了。单调栈复杂度 (O(n))
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100007
#define ll long long
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
struct Node{
int a,b; ll h;
bool operator <(const Node &x) const{
return b!=x.b? b>x.b:a>x.a;
}
}t[N],sta[N];
int n,top=0;
ll f[N];
inline ll max(ll x,ll y){return x>y? x:y;}
int main(){
n=read();
for(int i=1;i<=n;i++)
t[i].a=read(),t[i].b=read(),t[i].h=read();
sort(t+1,t+1+n);
ll ans=0;
for(int i=1;i<=n;i++){
while(top&&t[i].b<=sta[top].a) top--;
sta[++top]=t[i];
sta[top].h+=sta[top-1].h;
ans=max(ans,sta[top].h);
}
printf("%lld",ans);
}
发现不需要离散化了，瓶颈在于排序。如果再把快排换成基数排序，那么总的时间复杂度大概就是 (O(n))。
Tips
对于 (b_i=b_j)，要按照 (a) 降序排序，因为顶部的内径越小越好，对后面的转移有正的影响。