글 읽기 - 사수아탕? 질문입니다.

cmk5432 7년 전 0

이 문제를 아래 코드와 같이 재귀로 접근해 봤는데 왜 틀린지 이해가 가지 않네요... 설명 좀 부탁드립니다. 다른분들 코드 점화식을 보아도 비슷하게 생각한거 같은데... 어디를 놓진건지....

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

using namespace std;

int n, m;
int arrx[303];
int dp[303][303][2];


int fun(int left, int right, int w, int pm)
{
	if (left == 0 && right == n)
		return 0;
	else if (left<0 || right >n)
		return -987654321;
	int &ref = dp[left][right][w];
	if (ref != -1)
		return ref;
	
	if (w == 0)
	{
		ref = max(pm - (arrx[left] - arrx[left - 1]) + fun(left - 1, right, 0, pm - (arrx[left] - arrx[left - 1])), pm - (arrx[right + 1] - arrx[left]) + fun(left, right + 1, 1, pm - (arrx[right + 1] - arrx[left])));
	}
	else {
		ref = max(pm - (arrx[right] - arrx[left - 1]) + fun(left - 1, right, 0, pm - (arrx[right] - arrx[left - 1])), pm - (arrx[right + 1] - arrx[right]) + fun(left, right + 1, 1, pm - (arrx[right + 1] - arrx[right])));
	}
	if (ref < 0)
		ref = 0;
	return ref;
}


int main()
{

	memset(dp, -1, sizeof(dp));
	scanf("%d %d", &n, &m);
	for (int i =0; i<n; i++)
	{
		scanf("%d", &arrx[i]);
	}
	arrx[n] = 0;
	sort(arrx + 0, arrx + n+1);
	int start = 0;
	for (int i = 0; i <= n; i++)
	{
		if (arrx[i] == 0)
		{
			start = i;
			break;
		}
	}
	printf("%d\n", fun(start, start, 0, m));
}

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

문제

문제

출처

ICPC

사수아탕? 질문입니다.

cmk5432 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말