C++11(clang++ 3.9) 解法, 执行用时: 237ms, 内存消耗: 5348K, 提交时间: 2019-07-14 16:38:50

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define maxN 200005
LL n, L, v[maxN], a[maxN], T[maxN];
LL c[maxN];

void update(int i, LL x) {
  for (; i <= L; i += i & -i)
    T[i] = max(T[i], x);
}
LL query(int i) {
  LL ans = 0;
  for (; i; i -= i & -i)
    ans = max(ans, T[i]);
  return ans;
}
int main () {
  scanf("%d", &n);
  FOR(i, 0, n - 1) cin>>v[i],a[i] = v[i];
  FOR(i, 0, n - 1) cin>>c[i];
  sort(a, a + n);
  L = unique(a, a + n) - a;
  LL ans = 0, t;
  FOR(i, 0, n - 1) {
    int p = lower_bound(a, a + L, v[i]) - a + 1;
    t = query(p) + c[i];
    ans = max(ans, t);
    update(p, t);
  }
  cout<<ans<<endl;
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 247ms, 内存消耗: 5476K, 提交时间: 2019-07-19 15:10:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;

int n;
ll c[N],a[N],b[N],ans;
vector<ll>v;
 
int lb(int x){return x&(-x);}
void update(int x,ll k){
	while(x<N){
		c[x]=max(c[x],k);
		x+=lb(x);
	}
}
ll get_max(int x)
{
	ll res=0;
	while(x){
		res=max(res,c[x]);
		x-=lb(x);
	}return res;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		cin>>b[i];
		int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		ll tmp=get_max(x);
		ans=max(ans,b[i]+tmp);
		update(x,b[i]+tmp);	
	}
	cout<<ans<<endl;
	return 0;
}