Atcoder(134)E

E - Sequence Decomposing

---

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500500$ points

Problem Statement

You are given a sequence with $\mathrm{NN}$ integers: $\mathrm{A=\{A1,A2,\cdots ,AN\}A=\{A1,A2,\cdots ,AN\}}$. For each of these $\mathrm{NN}$ integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

• If ${\mathrm{AiAi}}^{}$ and ${\mathrm{AjAj}}^{}$ $(i<j)(i<j)$ are painted with the same color, ${\mathrm{Ai<AjAi<Aj}}^{}$.

Find the minimum number of colors required to satisfy the condition.

Constraints

• $\mathrm{1\le N\le 1051\le N\le 105}$
• $\mathrm{0\le Ai\le 1090\le Ai\le 109}$

---

Input

Input is given from Standard Input in the following format:

$\mathrm{NN}$
${\mathrm{A1A1}}^{}$
$::$
${\mathrm{ANAN}}^{}$

Output

Print the minimum number of colors required to satisfy the condition.

---

Sample Input 1 Copy

Copy

5
2
1
4
5
3

Sample Output 1 Copy

Copy

2

We can satisfy the condition with two colors by, for example, painting $22$ and $33$ red and painting $11$, $44$, and $55$ blue.

---

Sample Input 2 Copy

Copy

4
0
0
0
0

Sample Output 2 Copy

Copy

4

We have to paint all the integers with distinct colors.

题意：给定一个数字串，按照从前往后从小到大进行组合，最少能组合成几条这样的数字串。

利用STL进行模拟

数据范围是1e5，时间是2s，则算法需要nlgn

通过二分法进行查找，和for遍历一遍

算法1：

将数字串全部✖-1，进行反转，转化成从前往后从大到小进行组合；

通过vector数组进行模拟，利用upper_bound（）进行查找在其前边比其 大的值进行替换为本值，没有比其大的值就push_back（）此值，拿此值作为另一串的开头。

//lower_bound()和upper_bound()的区别

时间复杂度都是lgn

lower_bound(a.begin(),a,end(),key) 是查找大于等于key的位置

upper_bound(a.begin(),a.end(),key)是查找大于key 的位置

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int main ()
{
    int n;
    cin>>n;
    int a;
    vector<int>b;
    while(n--)
    {
        cin>>a;
        a*=-1;
        int it=upper_bound(b.begin(),b.end(),a)-b.begin();
        if(it==b.size())
        {
            b.push_back(a);
        }
        else
            b[it]=a;

    }
    cout<<b.size()<<endl;
    return 0;
}

算法2：利用deque//双端队列（速度非常快）

#include<iostream>
#include<deque>
using namespace std;

int main ()
{
    int n;
    cin>>n;
    int a;
    deque<int>b;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        int it= lower_bound(b.begin(),b.end(),a)-b.begin();
        if(!it)
            b.push_front(a);
        else
            b[it-1]=a;
    }
    cout<<b.size()<<endl;

    return 0;
}