글 읽기 - 왜 틀렸는지 모르겠습니다..ㅠㅠ

alohajihwan 7년 전 0

논리대로 진행 하였습니다.

multimap을 두어서 B배열에 어떤 인덱스가 들어 가있는지 저장하였고

LIS 알고리즘을 이용해 최단 경로 및 최소 거리 값을 계산 하였습니다.

어떤 부분에서 잘못되었는지 알려 주실 수 있을 까요? ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<string>
#include<map>
#include<string.h>
#include<stack>
#include<set>
using namespace std;
#define ll long long
#define INF 987654321

int N, M;
int A[555], B[555];
multimap<int, int>bm;
set<int>s;	
int dp[555][555];
int nex[555];
int maxV, e;
int solve(int n, int m)
{
	if (n == N) return 0;
	int & ret = dp[n + 1][m];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = n + 1; i < N; i++) {
		//B배열 안에 A[i]값이 있는 지 확인 && A[i]값과 같은 인덱스 전부 시도
		auto equalparis = bm.equal_range(A[i]);
		for (auto p = equalparis.first; p != equalparis.second; p++) {
			if (n == -1 || (A[n] < A[i] && p != bm.end() && m < p->second)) {
				if (n == -1 && p == bm.end()) continue;
				int rand = solve(i, p->second) + 1;
				if (ret < rand) {
					ret = rand;
					// 내 앞에 어디로 가야하는지 경로 저장
					nex[n + 1] = i + 1;
					if (maxV < ret) {
						maxV = ret;
						e = n + 1;
					}
				}
			}
		}
	}
	return ret;
}
vector<int>path;
void preserve(int d)
{
	if (nex[d] == -1) return;
	path.push_back(A[nex[d] - 1]);
	preserve(nex[d]);
}
int main()
{
	memset(nex, -1, sizeof(nex));
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		s.insert(A[i]);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> B[i];
		if (s.find(B[i]) != s.end())
			bm.insert(make_pair(B[i], i));
	}
	cout << solve(-1, 0) << endl;
	preserve(0);

	//reverse(path.begin(), path.end());
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << " ";
	cout << endl;
}

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다..ㅠㅠ

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말