글 읽기 - 대체 어떤 케이스에서 답이 안나오는 걸까요 ㅠㅠ

rhkdgus232 7년 전 0

혹시 아시는 분, 비슷한 상황 겪으신분 있으시면 알려주세요 ㅠ

#include <iostream>
using namespace std;
int n;
char cost[17][17];
int dp[1 << 17][17];
int artist[17];

void init() {
	for (int i = 0; i < 17; i++) {
		artist[i] = 1 << i;
	}
	for (int i = 0; i < (1 << 17); i++) {
		for (int j = 0; j < 17; j++) {
			dp[i][j] = -1;
		}
	}
}
int MAX(int a, int b) {
	if (a > b)return a;
	return b;
}
int process(int a, int pre, int pick, int cos) {
	if (pick >= n) return 1;
	if (dp[a][pre] != -1) return dp[a][pre];

	dp[a][pre] = 1;
	for (int i = 0; i < n; i++) {
		if (int(a&artist[i]) == 0 && cos <= cost[pre][i] - '0') {
			dp[a][pre] = MAX(dp[a][pre], process(a | artist[i], i, pick + 1, cost[pre][i] - '0') + 1);
		}
	}
	return dp[a][pre];

}

int main() {
	init();
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}
	cout << process(artist[0], 0, 1, 0) << endl;
}

etaehyun4 7년 전 1

점화식이 잘못된 것 같습니다. 위의 소스와 같이 하려면 점화식에 a, pre, cos의 정보까지 있는 3차원 배열이 되어야 합니다.

a, pre가 같다고 그 경우의 cos가 다 같은건 아니기 때문입니다.

rhkdgus232 7년 전 0

etaehyun4

다행히 전날밤에 찾아서 맞았어요!! 하지만 그래도 알려주셔서 고맙습니다.

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

문제

문제

출처

ICPC

대체 어떤 케이스에서 답이 안나오는 걸까요 ㅠㅠ

rhkdgus232 7년 전 0

etaehyun4 7년 전 1

rhkdgus232 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말