补充二分LIS
B3637 最长上升子序列
题目描述
这是一个简单的动规板子题。
给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
输入格式
第一行，一个整数 n n n，表示序列长度。
第二行有 n n n 个整数，表示这个序列。
输出格式
一个整数表示答案。
输入输出样例 #1
输入 #1
6
1 2 4 1 3 4
输出 #1
4
说明/提示
分别取出 1 1 1、 2 2 2、 3 3 3、 4 4 4 即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n,a[N],b[N];
int len = 1;
int j;
int find(int x){
int l = 1,r = len,mid;
while(l <= r){
mid = (l+r)/2;
if(x > b[mid])l = mid+1;
else r = mid-1;
}
return l;
}
int main(){
cin >> n;
for(int i = 1;i<=n;i++)cin >> a[i];
b[1] = a[1];
for(int i = 2;i<=n;i++){
if(a[i] > b[len]){
b[++len] = a[i];
}else{
j = find(a[i]);
b[j] = a[i];
}
}
cout << len;
return 0;
}