글 읽기 - 반례 하.. 몇시간동안 ㅠㅠㅠ 했는데

ppqhdl2 4년 전 0

반례좀 찾아주세요 하 .. 도저히 뭐가 잘못된건지 .. (11%에서 ..)

#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>
#define S 0
#define E 987654321
using namespace std;

struct info {
	int line;
	int idx;
	int pos;
	info() {
		line = idx = pos = S;
	}
};

int input[10];
info h_info[4];
int inner[4][8] = {

	{0,0,0,0,0,0,0,0},
	{0,13,16,19,25,30,35,40},
	{0,22,24,25,30,35,40,0},
	{0,28,27,26,25,30,35,40}

};

bool IsOther(int idx, int line, int pos) {
	if (pos == E)return false;

	for (int i = 0; i < 4; i++) {
		if (i == idx)continue;
		if (pos == 40 && h_info[i].pos == 40)return true;
		if (line == 0) {
			if (line == h_info[i].line && pos == h_info[i].pos)return true;
		}
		else {
			if (h_info[i].line != 0 && pos == h_info[i].pos)return true;
		}

	}

	return false;
}
int ans = -1;

void dfs(int idx, int sum) {
	if (idx == 10) {
		ans = ans > sum ? ans : sum;

		return;
	}
	for (int i = 0; i < 4; i++) {
		int prev_line = h_info[i].line, prev_idx = h_info[i].idx, prev_pos = h_info[i].pos;
		if (prev_pos == E)continue;
		if (prev_line == 0) {
			int new_idx = prev_idx + input[idx], new_pos = new_idx * 2;
			int new_line = prev_line;
			if (new_pos == 10) {
				new_line = 1; new_idx = 0;
			}
			else if (new_pos == 20) {
				new_line = 2; new_idx = 0;
			}
			else if (new_pos == 30) {
				new_line = 3; new_idx = 0;
			}
			int add = new_pos;
			if (new_pos > 40)add = 0, new_pos = E;

			if (IsOther(i, new_line, new_pos))continue;

			h_info[i].line = new_line, h_info[i].idx = new_idx, h_info[i].pos = new_pos;

			dfs(idx + 1, sum + add);

			h_info[i].line = prev_line, h_info[i].idx = prev_idx, h_info[i].pos = prev_pos;
		}
		else {
			int new_idx = prev_idx + input[idx]; int new_pos;
			int add = 0;
			if ((prev_line == 1 && new_idx > 7) || (prev_line == 2 && new_idx > 6) || (prev_line == 3 && new_idx > 7))new_pos = E;
			else add = new_pos = inner[prev_line][new_idx];

			if (IsOther(i, prev_line, new_pos))continue;

			h_info[i].idx = new_idx, h_info[i].pos = new_pos;

			dfs(idx + 1, sum + add);

			h_info[i].idx = prev_idx, h_info[i].pos = prev_pos;
		}
	}

}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);

	for (int i = 0; i < 10; i++)cin >> input[i];
	//cout << h_info[0].pos << endl;
	dfs(0, 0);

	cout << ans << endl;

	return 0;
}

ppqhdl2 4년 전 0

30이 2개 있었넹; ㅠ

c9boom7 4년 전 1

16,22,26,28도 각각 2개씩 있네요

만약 방문처리를 경로별로 하지 않고 21칸짜리 배열에 한번에 하시는 분들은

16,22,26,28,30 에 대해서 고려하셔야 합니다!!!

이거때매 2일동안 고민했네요ㅠㅠ

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

문제

문제

출처

ICPC

반례 하.. 몇시간동안 ㅠㅠㅠ 했는데

ppqhdl2 4년 전 0

ppqhdl2 4년 전 0

c9boom7 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말