글 읽기 - 반례 부탁드립니다.

kinssang 6년 전 0

dp 형식은 이렇습니다

문제의 답 = min(1번 사건을 1번 경찰차가 처리했을 때의 최소값, 1번 사건을 2번 경찰차가 처리했을 때의 최소값)

1번 사건을 1번 경찰차가 처리했을 때의 최소값 = min(2번 사건을 1번 경찰차가 처리했을때의 최소값, 2번 사건을 2번 경찰차가 처리했을 때의 최소값)

dp[i][j] = 첫번째 경찰차가 i, 두번째 경찰차가 j에 도달한 상태에서, 사건을 끝까지 진행할 때 더해지는 거리 중 가장 최소의 거리.

이런식으로 했는데 시작하자마자 틀렸습니다가 뜨네요.

KOI 기출인데 TC도 못찾겠어서 도움 요청드립니다.

#include <stdio.h>

int dp[1000][1000];
int root[1000][1000];

int inline abs(int a)
{
	return (a < 0) ? ((-1)*a) : a;
}

int main()
{
	int N, W, input[1001][2];
	scanf("%d%d", &N, &W);
	for (int i = 1; i <= W; i++) scanf("%d%d", &input[i][0], &input[i][1]);
	for (int i = W - 1; i >= 1; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (j == 0)
			{
				if (dp[i][i + 1] + (N - input[i + 1][0]) + (N - input[i + 1][1]) < dp[i + 1][j] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]))
				{
					root[i][j] = 2;
					dp[i][j] = dp[i][i + 1] + (N - input[i + 1][0]) + (N - input[i + 1][1]);
				}
				else
				{
					root[i][j] = 1;
					dp[i][j] = dp[i + 1][j] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]);
				}
				if (dp[i + 1][i] + input[i + 1][0]-1 + input[i + 1][1]-1 < dp[j][i + 1] + abs(input[i + 1][0] - input[i][0]) + abs(input[i + 1][1] - input[i][1]))
				{
					root[j][i] = 1;
					dp[j][i] = dp[i + 1][i] + input[i + 1][0]-1 + input[i + 1][1]-1;
				}
				else
				{
					root[j][i] = 2;
					dp[j][i] = dp[j][i + 1] + abs(input[i + 1][0] - input[i][0]) + abs(input[i + 1][1] - input[i][1]);
				}
			}
			else
			{
				if (dp[i][i + 1] + abs(input[j][0] - input[i + 1][0]) + abs(input[j][1] - input[i + 1][1]) < dp[i + 1][j] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]))
				{
					root[i][j] = 2;
					dp[i][j] = dp[i][i + 1] + abs(input[j][0] - input[i + 1][0]) + abs(input[j][1] - input[i + 1][1]);
				}
				else
				{
					root[i][j] = 1;
					dp[i][j] = dp[i + 1][j] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]);
				}
				if (dp[i + 1][i] + abs(input[j][0] - input[i + 1][0]) + abs(input[j][1] - input[i + 1][1]) < dp[j][i + 1] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]))
				{
					root[j][i] = 1;
					dp[j][i] = dp[i + 1][i] + abs(input[j][0] - input[i + 1][0]) + abs(input[j][1] - input[i + 1][1]);
				}
				else
				{
					root[j][i] = 2;
					dp[j][i] = dp[j][i + 1] + abs(input[i][0] - input[i + 1][0]) + abs(input[i][1] - input[i + 1][1]);
				}
			}
		}
	}
	int cur, i=0, j=0;
	if (dp[0][1] + N - input[1][0] + N - input[1][1] < dp[1][0] + input[1][0] + input[1][1] - 2)
	{
		printf("%d\n", dp[0][1] + N - input[1][0] + N - input[1][1]);
		cur = 2;
	}
	else
	{
		printf("%d\n", dp[1][0] + input[1][0] + input[1][1] - 2);
		cur = 1;
	}
	for(int k=1;k<=W;k++)
	{
		printf("%d\n", cur);
		if (cur == 2) j = k;
		else i = k;
		cur = root[i][j];
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례 부탁드립니다.

kinssang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말