洛谷P1020 导弹拦截

发表于 更新于 分类于 本文字数： 107 阅读时长 ≈ 1 分钟

第一问是求最长不升子序列，第二问是求最长上升子序列

对于第一问利用vector的反向迭代器来转换为最长不降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL x;
vi v(1, -1),j(1,-1),s;
int main()
{
    while (scanf("%lld",&x)==1)
    {
        s.pb(x);
        if (x > v.back())
            v.pb(x);
        else
            *lower_bound(all(v), x) = x;
    }
    for(auto it=s.rbegin();it!=s.rend();it++){
        if((*it)>=j.back())
        j.pb(*it);
        else *upper_bound(all(j),*it)=*it;
    }
    cout<<j.size()-1<<"\n";
    cout << v.size()-1;
    return 0;
}