codeforces gym 100553I

solution

令a[i]表示位置i的船的编号

研究可以发现，应是从中间开始，往两边跳。。。。

于是就是一个点往两边的最长下降子序列之和减一

魔改树状数组求min

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 200005

using namespace std;

int n,x,a[maxn],l[maxn],r[maxn];

int tl[maxn],tr[maxn];

int al(int k){

    int sum=0;

    for(int i=k;i;i-=i&-i)sum=max(sum,tl[i]);

    return sum;

}

void jl(int k,int v){

    for(int i=k;i<=n;i+=i&-i)tl[i]=max(tl[i],v);

}

int ar(int k){

    int sum=0;

    for(int i=k;i;i-=i&-i)sum=max(sum,tr[i]);

    return sum;

}

void jr(int k,int v){

    for(int i=k;i<=n;i+=i&-i)tr[i]=max(tr[i],v);

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

        scanf("%d",&x);a[x]=i;

    }

    for(int i=1;i<=n;i++){

        l[i]=al(a[i])+1;

        jl(a[i],l[i]);

    }

    for(int i=n;i>=1;i--){

        r[i]=ar(a[i])+1;

        jr(a[i],r[i]);

    }

    int ans=0;

    for(int i=1;i<=n;i++){

        ans=max(ans,l[i]+r[i]-1);

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

codeforces gym 100553I

最新文章

热门文章