글 읽기 - 반례좀 주시면 감사하겠습니다.

okmy729 3년 전 0

이 문제는 단순 LIS 문제 아닌가요??

반례좀 주시면 감사하겠습니다.

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int main(){
	fastio;
	long long int n,a;
	cin>>n;
	vector<long long int> v(1,-1000000001 );
	for(int i=0;i<n;i++){
		cin>>a;
		if(v.back()<a) v.push_back(a);
		//else *lower_bound(v.begin(),v.end(),a)=a;
	}
	cout<<v.size()-1<<"\n";
	for(int i=1;i<v.size();i++) cout<<v[i]<<" ";
}

mc_progw12 3년 전 3

LIS NlogN 기법을 사용할 때 이용되는 벡터의 원소의 구성은 실제 LIS와는 무관하다고 알고 있어요

12행의 주석을 그대로 두면
4
100 20 30 40

answer
3
20 30 40
result
1
100

12행의 주석을 코드로 살려내면
4
10 20 30 5
    
answer
3
10 20 30
result
3
5 20 30

okmy729 3년 전 0

답변 감사합니다.

그러면 출력을 어떻게 해줘야 하나요??

djm03178 3년 전 1

dp값을 갱신할 때 그 이전의 원소가 무엇이었는지를 같이 기억해두면 됩니다.

mc_progw12 3년 전 1

자세한건 블로그에..

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

문제

문제

출처

ICPC

반례좀 주시면 감사하겠습니다.

okmy729 3년 전 0

mc_progw12 3년 전 3

okmy729 3년 전 0

djm03178 3년 전 1

mc_progw12 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말