글 읽기 - 어디서 틀렸는지 모르겠습니다...

tepmilk 3년 전 3

코드 자체는 전구를 입력 받을 때 인덱스를 저장해서 그 값을 토대로 LIS를 구한 후 그걸 역추적하는 코드로 짰습니다만.. 28%에서 틀렸다고 나오네요.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int S[10001]; // n번째에 몇 번 switch가 있는 지 저장
int L[10001]; // n번 전구가 배치된 순서를 저장
int cache[10001];
int choice[10001];


int lis2(int start) {
	int& res = cache[start];

	if (res != -1) return res;
	res = 1;
	int bestNext = -1;
	for (int i = start ; i < N; i++) {
		if (start == -1 ||  L[S[start]] < L[S[i]] ) {
			int cand = lis2(i) + 1;
			if (cand > res) {
				res = cand;
				bestNext = i;
			}
		}
		
	}
	choice[start + 1] = bestNext;
	return res;
}

void reconstruct(int start, vector<int>& seq) {
	if (start != -1) seq.push_back(S[start]);
	int next = choice[start + 1];
	if (next != -1) reconstruct(next, seq);
}
int main(void) {
	int result , maxi=-1;
	vector<int> seq;
	fill(S, S + 10001, -1);
	fill(L, L + 10001, -1);
	fill(cache, cache + 10001, -1);
	fill(choice, choice + 10001, -1);
	
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		//
		cin >> S[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> result;
		L[result] = i;
	}
	
	result = 1;
	for (int i = N-1; i >=0; i--) {
		int tmp = lis2(i);
		if (result < tmp) {
			result = tmp;
			maxi = i;
		}
	}
	reconstruct(maxi, seq);
	
	sort(seq.begin(), seq.end());

	cout << result << endl;

	for (int i = 0; i < seq.size(); i++) {
		cout << seq[i] << " ";
	}

	cout << endl;
	return 0;
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다...

tepmilk 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말