序列划分数

狄尔沃斯定理的划分数和序列长度:
不升(下降)————上升
不降(上升)————下降

#include<bits/stdc++.h>
using namespace std;
int const N=1e5+7;
int n,a[N];
vector<int>v;
int main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=n;++i){
        int z=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        if(z==v.size()) v.push_back(a[i]);
        else v[z]=a[i];
    }
    cout << v.size();
    return 0;
}

//

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) x&(-x)
int const N=1e5+7;
int n;
ll tr[N];
void add(ll w,ll p){
    for(;p<=n;p+=low(p)){
        tr[p]=max(tr[p],w);
    }
}
ll ask(ll p){
    ll res=0;
    for(;p;p-=low(p)) res=max(res,tr[p]);
    return res;
}
int main(){
    cin >> n;
    for(int i=1,x;i<=n;++i){
        cin >> x;
        add(ask(x-1)+1,x);
    }
    cout << ask(n);
    return 0;
}
全部评论

相关推荐

10-19 14:15
兰州大学 Java
黄花菜豆:咱俩bg很一致啊uu而且我也做过这个仿小红书,感觉有点太深了短期内不好驾驭啊怕被问穿
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务