题目：https://ac.nowcoder.com/acm/contest/992/B

 

这道题目的思想和这一道小石的妹子感觉有点像，有兴趣的话可以去看看这一道题，这是我写的题解：https://blog.csdn.net/xiaonanxinyi/article/details/95758719

 

本题思路：假设我们现在处在第k个位置，那么为了使我们可以得到最优的解，我们是不是要找到后面的所有比这高的位置里的最优的一个，说道这其实和上面的题目就差不多了。那么既然我们需要后面的最优解，那么何不倒着做呢。那就是把高度离散化一下，再把位置对称一下就好了。 具体看代码：

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100*1000*2+10;
int a[N],h[N];
int b[N],cnt=1;
ll s[N];
ll f[N];
int n,len;
int lowerbit(int x){return x&-x;}
void add(int x,ll k){while(x<=n)s[x]=max(s[x],k),x+=lowerbit(x);}
ll ask(int x){ll ans=0;while(x)ans=max(ans,s[x]),x-=lowerbit(x);return ans;}
int getid(int x){return lower_bound(b+1,b+1+len,x)-b;};

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",h+i),b[i]=h[i];
    for(int i=1;i<=n;i++)scanf("%d",a+i);

    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b;
    len--;
    ll ans=0;
    for(int i=n;i>=1;i--){
        int k=getid(h[i]);
        ll flag=ask(len-k+1);
        ans=max(ans,flag+a[i]);
        f[k]=max(f[k],flag+a[i]);
        add(len-k+1,f[k]);
    }

    printf("%lld\n",ans);

    return 0;
}