글 읽기 - MT 반례를 못찾겠습니다.

wl9322 3년 전 0

인터넷에 돌아다니는 예제 및 테스트 케이스 전부다 해보았지만 현재까지 잘못된 답이 도출 된 적이 없습니다. 그래서 반례를 알려주시면 감사하겠습니다.

코드의 방식은 싸이클의 필수적인 사람의 수를 cnt에 저장하였고 그외에 가도되고 안가도 되는 인원들을 var_cnt에 저장하였습니다.

싸이클을 구한 후 가변인원까지 더해서 dp를 채워 풀었습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct cycle {
	int cnt;
	int var_cnt;
};

vector<cycle> cycles;
vector<int> cycle_number;
vector<int> node;
vector<bool> visited;
vector<vector<int>> dp;

cycle var_check(int cnt, int start) {
	cycle result;
	result.cnt = 1;
	result.var_cnt = cnt - 1;
	int next = node[start];

	while (next != start) {
		++result.cnt;
		--result.var_cnt;
		next = node[next];
	}

	return result;
}

void cycle_dfs(int cnt, int start) {
	if (!visited[start]) {
		++cnt;
		visited[start] = true;
		int next = node[start];
		cycle_dfs(cnt, next);
		cycle_number[start] = cycle_number[next];
	}

	else {
		if (cycle_number[start] == -1) {
			cycle temp = var_check(cnt, start);
			cycle_number[start] = cycles.size();
			cycles.push_back(temp);
		}
		else {
			++cycles[cycle_number[start]].var_cnt;
		}
	}
}

void first_dfs(int cnt, int start) {
	if (!visited[start]) {
		++cnt;
		visited[start] = true;
		int next = node[start];
		cycle_dfs(cnt, next);
		cycle_number[start] = cycle_number[next];
	}
}

int main() {
	int N, K, input;

	cin >> N >> K;

	visited.resize(N, false);
	cycle_number.resize(N, -1);

	for (int idx = 0; idx < N; ++idx) {
		cin >> input;
		node.push_back(input - 1);
	}

	for (int idx = 0; idx < N; ++idx) {
		first_dfs(0, idx);
	}

	dp.resize(cycles.size() + 1);
	dp[0].resize(K + 1);
	for (int idx = 1; idx < dp.size(); ++idx) {
		dp[idx].resize(K + 1);
		dp[idx][0] = 0;
		for (int j = 1; j <= K; ++j) {
			if (j >= cycles[idx - 1].cnt) {
				dp[idx][j] = max(cycles[idx - 1].cnt + cycles[idx - 1].var_cnt + dp[idx - 1][j - cycles[idx - 1].cnt], dp[idx-1][j]);
			}
			else {
				dp[idx][j] = dp[idx - 1][j];
			}
		}
	}

	if (dp[cycles.size()][K] < K) cout << dp[cycles.size()][K];
	else cout << K;

	return 0;
}

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

문제

문제

출처

ICPC

MT 반례를 못찾겠습니다.

wl9322 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말