글 읽기 - 이문제 일반적인 NlogN의 LIS문제 아닌가요??

jjongwuner 6년 전 0

50%가서 틀리다고 나와가지고 궁금해서 엿쭤봅니다 ~!

#include<iostream>
#include<vector>
using namespace std;
int n, tmp;
vector<int> a, lis;
int main() {
	scanf("%d", &n);
	a.resize(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < n; i++) {
		if (a[i] > tmp) lis.push_back(a[i]);
		else {
			int L = 0, R = lis.size() - 1, M;
			while (L != R) {
				M = (L + R) / 2;
				if (lis[M] > a[i]) R = M;
				else L = M + 1;
			}
			lis[L] = a[i];
		}
		tmp = lis[lis.size() - 1];
	}
	printf("%d\n",lis.size());
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이문제 일반적인 NlogN의 LIS문제 아닌가요??

jjongwuner 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말