LIS
\operatorname{LIS}
LIS
题目链接：
AtCoder Chokudai SpeedRun 001 H
\operatorname{AtCoder\ Chokudai\ SpeedRun\ 001\ H}
AtCoder Chokudai SpeedRun 001 H /
luogu AT2827
\operatorname{luogu\ AT2827}
luogu AT2827
题目大意
来自洛谷：
样例输入1
5
3 1 5 4 2
样例输出1
2
样例输入2
6
1 2 3 4 5 6
样例输出2
6
样例输入3
7
7 6 5 4 3 2 1
样例输出3
1
样例输入4
20
19 11 10 7 8 9 17 18 20 4 3 15 16 1 5 14 6 2 13 12
样例输出4
6
数据范围
1
≤
N
≤
100
,
000
1\leq N\leq 100,000
1≤N≤100,000
思路
就是一道普通的 LIS 。
就按 nlogn 的算法来做即可。
洛谷交不了，可以在 AtCoder 上面交。
点我查看 LIS 模板题的题解！
代码
#include<cstdio>
#include<iostream>
using namespace std
;
int n
, a
[100001], shang
[100001], lef
, righ
, shang_num
;
int main() {
shang
[0] = -2147483647;
scanf("%d", &n
);
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &a
[i
]);
if (a
[i
] > shang
[shang_num
]) {
shang_num
++;
shang
[shang_num
] = a
[i
];
}
else {
lef
= 0, righ
= shang_num
;
while (lef
< righ
) {
int mid
= (lef
+ righ
) >> 1;
if (shang
[mid
] >= a
[i
]) righ
= mid
;
else lef
= mid
+ 1;
}
shang
[lef
] = min(shang
[lef
], a
[i
]);
}
}
printf("%d", shang_num
);
return 0;
}
