@zzzc18
2017-10-26T07:22:51.000000Z
字数 2193
阅读 922
线段树
我可以说不会正解么?
也相当于DP,对于当前的数值,我们求以这个数为波峰/波谷结尾的最长的波峰、波谷交替的序列,这样就可以用线段树维护值域,每个值对应的是以这个值结尾的最长的满足条件的数列长度
在这里
for(i=2;i<=N;i++){
int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;
int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;
F.modify(1,num[i],val_g+1,val_f+1);
}
就是以当前数为波峰的数列长度
就是以当前数为波谷的数列长度
将这个数值插入线段树时,将上面求的两个值+1再交换(波峰波谷交替)就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100000+9;
int b[MAXN];
int num[MAXN];
int n,N;
class Segment_Tree{
private:
struct T{
int ls,rs,left_range,right_range;
int val_f;
int val_g;
}tree[MAXN*4];
int lazy_min[MAXN*4];
int lazy_max[MAXN*4];
int cnt;
void update(int x){
tree[x].val_f=max(tree[tree[x].ls].val_f,tree[tree[x].rs].val_f);
tree[x].val_g=max(tree[tree[x].ls].val_g,tree[tree[x].rs].val_g);
}
public:
int Build(int l,int r){
int now=++cnt;
tree[now].left_range=l;
tree[now].right_range=r;
if(l==r){
return now;
}
int mid=l+r>>1;
tree[now].ls=Build(l,mid);
tree[now].rs=Build(mid+1,r);
update(now);
return now;
}
int getmax_f(int k,int l,int r){
if(l<=tree[k].left_range && tree[k].right_range<=r){
return tree[k].val_f;
}
int mid=tree[k].left_range+tree[k].right_range>>1;
int re=-1;
if(l<=mid)re=max(re,getmax_f(tree[k].ls,l,r));
if(r>=mid+1) re=max(re,getmax_f(tree[k].rs,l,r));
return re;
}
int getmax_g(int k,int l,int r){
if(l<=tree[k].left_range && tree[k].right_range<=r){
return tree[k].val_g;
}
int mid=tree[k].left_range+tree[k].right_range>>1;
int re=-1;
if(l<=mid)re=max(re,getmax_g(tree[k].ls,l,r));
if(r>=mid+1) re=max(re,getmax_g(tree[k].rs,l,r));
return re;
}
void modify(int k,int pos,int val1,int val2){
if(tree[k].left_range==tree[k].right_range){
tree[k].val_f=val1;
tree[k].val_g=val2;
return;
}
int mid=tree[k].left_range+tree[k].right_range>>1;
if(pos<=mid)modify(tree[k].ls,pos,val1,val2);
else modify(tree[k].rs,pos,val1,val2);
update(k);
}
}F;
int main(){
scanf("%d",&N);
int i;
for(i=1;i<=N;i++){
scanf("%d",&num[i]);
b[i]=num[i];
}
sort(b+1,b+N+1);
n=unique(b+1,b+N+1)-(b+1);
for(i=1;i<=N;i++)
num[i]=lower_bound(b+1,b+n+1,num[i])-b;
F.Build(1,n);
F.modify(1,num[1],1,1);
int ans;
for(i=2;i<=N;i++){
int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;
int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;
F.modify(1,num[i],val_g+1,val_f+1);
}
printf("%d\n",max(F.getmax_f(1,1,n),F.getmax_g(1,1,n)));
return 0;
}