글 읽기 - 어떤 경우에 틀릴까요..?

mastojun 8년 전 2

http://www.csc.kth.se/contest/boi/beetle-spoiler.p... 에 나와있는대로 풀었(다고 생각..)습니다.
솔류션의 함수 L과 함수 R에서 i, j와 제 코드 left, right의 i, r의 의미는 다릅니다만 전체적으로 같은 로직입니다.

left(l, r, remain) 에서 l 은 현재 수아의 위치, r은 수아가 다음에 갈 수 있는 위치, remain은 남은 방문 횟수
right(l, r, remain)에서 l 은 수아가 다음에 갈 수 있는 위치, r은 현재 수아의 위치, remain은 남은 방문 횟수

http://www.csc.kth.se/contest/boi/tasks.php 에서 구할 수 있는 테스트 케이스로도 돌려봤는데, 제공된 45개의 테스트에서는 모두 정답이 나옵니다.

아마 여기서 제공하는 다른 코너케이스를 통과 못하거나 하는거 같은데, 어디가 문제있는지 모르겠네요 @_@;

... 입력의 최대의 경우에도 오버플로우는 발생할 것 같지 않은데....

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

int n, m;
int candy[301];
int leftDp[302][302];
int rightDp[302][302];

int right(int l, int r, int remain);

int left(int l, int r, int remain) {
	if (remain == 0) return 0;

	int& result = leftDp[l][r];
	if (result != -1) return result;
	result = INT_MAX;
	if (l > 0) {
		result = remain * (candy[l] - candy[l - 1]) + left(l - 1, r, remain - 1);
	}
	if (r <= n) {
		result = min(result, remain * (candy[r] - candy[l]) + right(l - 1, r, remain - 1));
	}

	return result;
}

int right(int l, int r, int remain) {
	if (remain == 0) return 0;

	int& result = rightDp[l][r];
	if (result != -1) return result;
	result = INT_MAX;
	if (r < n) {
		result = remain * (candy[r + 1] - candy[r]) + right(l, r + 1, remain - 1);
	}
	if (l >= 0) {
		result = min(result, remain * (candy[r] - candy[l]) + left(l, r + 1, remain - 1));
	}

	return result;
}

int main() {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		scanf("%d", candy + i);
	}

	candy[n] = 0;

	sort(candy, candy + n + 1);

	int zeroIndex = 0;
	for (int i = 0; i <= n; i++) {
		if (candy[i] == 0) {
			zeroIndex = i;
			break;
		}
	}
	int result = 0;
	for (int i = 0; i <= n; i++) {
		memset(leftDp, -1, sizeof(leftDp));
		memset(rightDp, -1, sizeof(rightDp));
		result = max(result, m * i - left(zeroIndex, zeroIndex + 1, i));
	}
	printf("%d\n", result);

	return 0;
}

mastojun 8년 전 0

오! 감사합니다.

r은 검토해본 기억이 나는데 l은 안했....

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

문제

문제

출처

ICPC

어떤 경우에 틀릴까요..?

mastojun 8년 전 2

mastojun 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말