DP单调栈优化

看到这道题可以很自然的想到DP

设$dp[i]$表示最后一个$ring$为$i$的最大高度

首先将$b$为第一关键字，$a$为第二关键字，升序排序元素

那么对于$i$来说，它下面的$ring$的所有能转移过来的$j$，要满足$ja[j]$

所以dp转移方程为$dp[i]=max{dp[j]}+h[i](ja[j])$

但这个转移时$O(n^{2})$的

那么需要找出满足条件的最大$dp$值

发现对于$ia[i]$,$b[k]>a[j]$

$dp[i]<dp[j]<dp[k]$，那么最后的元素就一定最优，且如果有其他不满足关系，对之后没有影响

那么可以用单调栈维护信息

#include
#define ll long long
using namespace std;
const ll MAXN=1e5+10;
ll n,dp[MAXN];
struct node
{
ll a,b,h;
}sh[MAXN];
bool cmp(node a,node b)
{
return (a.b>b.b || (a.b==b.b && a.a>b.a));//排序
}
int main()
{
scanf("%lld",&n);
for (ll i=1;i<=n;i++) scanf("%lld%lld%lld",&sh[i].a,&sh[i].b,&sh[i].h); sort(sh+1,sh+1+n,cmp); stack s;
for (ll i=1;i<=n;i++) { while (!s.empty() && sh[s.top()].a>=sh[i].b)//单调栈维护信息
s.pop();
if (!s.empty())
dp[i]=dp[s.top()];//转移
dp[i]+=sh[i].h;
s.push(i);
}
ll ans=0;
for (ll i=1;i<=n;i++)
ans=max(ans,dp[i]);
printf("%lld\n",ans);
}