글 읽기 - 질문입니다.

cmk5432 7년 전 0

다른분들 코드를 보니

reg = max(max(fun(index + 2, count+1)+arr[index], fun(index+1, count)+arr[index]),fun(index+1, count));

이렇게 구현한 점화식 부분을 for문으로 한 구간이 될수 있는 부분을 더해주던데...

fun(index+1, count)+arr[index] 이렇게 하여 다음 함수로 넘어가는 과정이 결국에는 구간을 for문으로 더해주는 것과 같아지는게 아닌가요?

어디서 예외가 있는지 잘 모르겠습니다. ㅠㅠ

반례라도..

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m;
int arr[110];
int dp[111][111];

int fun(int index,int count)
{
	if (count == m)
		return 0;
	if(index>=n)
		return -987654321;

	int &reg = dp[index][count];
	if (reg != -1)
		return reg;
	
	reg = max(max(fun(index + 2, count+1)+arr[index], fun(index+1, count)+arr[index]),fun(index+1, count));
	
    return reg;

}

int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d %d", &n, &m);
	for (int i =0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	printf("%d\n", fun(0, 0));
	return 0;
}

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

문제

문제

출처

ICPC

질문입니다.

cmk5432 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말