글 읽기 - 25%에서 틀리는데 반례를 못찾겠습니다..ㅠㅠ

sotter1020 5년 전 0

문제가 어렵다고 생각안했는데..ㅠㅠ

뭐가 문제일까요?

주석있습니돠 ㅠㅠ

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[11][1 << 11];
int s[11][11], TC;
int solution(int p, int state) {
	if (state == (1 << 11) - 1) return 0; // 포지션이 정해지면 return 0;
	int& ret = dp[p][state];
	if (ret != 0) return ret;
	for (int t = 0; t < 11; ++t)
		if ((state >> t) % 2 == 0 && s[p][t] != 0) // 포지션이 0이 아니고 정해지지 않는 포지션일 경우
			ret = max(ret, solution(p+1, state | 1 << t) + s[p][t]); // 해당 포지션 능력치를 더함
	return ret;
}
int main() {
	cin >> TC;
	while (TC--) {
		memset(dp, 0, sizeof(dp));
		for (int y = 0; y < 11; ++y)
			for (int x = 0; x < 11; ++x)
				cin >> s[y][x];
		cout << solution(0, 0) << '\n';
	}
	return 0;
}

newdeal 5년 전 7

안녕하세요.

반례 첨부해 드립니다.

코드의 잘못된 점은 올바르지 않은 선수조합이라도 값에 반영을 한다는 점입니다.

반례에있는 (0,0), (1,1), (2,2)를 선택을 한후, 이코드는 (3,2)에서 더이상 선택을 하지못하고 그대로 ret을 리턴하면서, max값을 30으로 만들어 버립니다.

하지만 이 조합은 단 3명의 선수만을 조합한것이므로, 올바르지 않은 선수조합이 되어버립니다.

1
0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
0 10 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
//your answer:30
//correct answer:29

sotter1020 5년 전 1

아! 이해했습니다! 감사합니다

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

문제

문제

출처

ICPC

25%에서 틀리는데 반례를 못찾겠습니다..ㅠㅠ

sotter1020 5년 전 0

newdeal 5년 전 7

sotter1020 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말