链接:https://ac.nowcoder.com/acm/contest/992/B
来源:牛客网
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
在之前很火的一个动漫《干物妹小埋》中,大家对小埋打游戏喝可乐的印象十分的深刻。 现在欧尼酱将小埋的快乐水全部分开藏在了家具的顶端。 小埋使出空中1080°转身接战术翻滚跳到任一家具上,她相信,只要她翻滚的足够快,欧尼酱就跟不上她。 1.为获取梦幻开局,小埋一套技能可以使她一开始掉落在任一家具上。 2.小埋家的家具按顺序给出,每个家具可跳可不跳,为避开欧尼酱的追击,小埋翻滚到某个家具上面后,只能向前继续翻滚。 3.启动超重力感应系统的小埋不会从较高的家具翻滚到较低的家具上。 4.由于每个家具上的快乐水都有对应的happy值,IQ==250的小埋会选择一条happy值总和最大的路线。 那么,最终小埋将获得的happy值总和是多少呢?输入描述:
第一行一个整数n(0<n<=200000),表示小埋家的家具数。
第二行n个整数,对于每个整数ai, 0<=ai<=10^9,表示第i个家具的高度。
第三行n个整数,对于每个整数vi, 0<=vi<=10^9,表示第i个家具上的快乐水的happy值。
输出描述:
一个整数,表示小埋获得的happy值总和。示例1
输入
复制6 2 1 1 3 3 4 3 1 1 1 1 1
输出
复制6
说明
路线:2->3->3->4
答案:3+1+1+1
解题思路:将a值从小到大排序,如果a值相同把编号小的放前面,然后用线段树维护happy值总和的最大值,每次查找比小于当前编号的最大happy值,如果加上当前happy大于答案,则对答案进行更新。然后在将该happy值更新到线段树中。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=200005; int n; struct node{ int id; ll a,v; }p[maxn]; bool cmp(node x,node y){ if(x.a==y.a) return x.id<y.id; return x.a<y.a; } ll tree[maxn*4]; void pushup(int rt){ tree[rt]=max(tree[rt<<1],tree[rt<<1|1]); } void update(int pos,ll val,int l,int r,int rt){ if(l==r){ tree[rt]+=val; return; } int mid=l+r>>1; if(mid>=pos) update(pos,val,l,mid,rt<<1); if(mid<pos) update(pos,val,mid+1,r,rt<<1|1); pushup(rt); } ll ask(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return tree[rt]; ll ans=0; int mid=l+r>>1; if(mid>=L) ans=max(ans,ask(L,R,l,mid,rt<<1)); if(mid<R) ans=max(ans,ask(L,R,mid+1,r,rt<<1|1)); return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&p[i].a); for(int i=1;i<=n;i++) { scanf("%lld",&p[i].v); p[i].id=i; } sort(p+1,p+1+n,cmp); ll ans=0; for(int i=1;i<=n;i++){ ll Max=ask(1,p[i].id,1,n,1); //询问比当前编号小的happy总和最大值 ans=max(ans,Max+p[i].v); //更新答案 update(p[i].id,Max+p[i].v,1,n,1); //将该happy更新到区间中 } cout<<ans<<endl; return 0; }