글 읽기 - 반례를 찾을 수 없어요 ㅠㅠ 맞은 것 같지만...

tddhot2 7년 전 0

어떤 반례가 있을련지 모르겠어요

이전에 질문들을 다 보면서 반례들을 테스트해봤지만 전부다 정답인데...

올라가다가 실패하네요 ㅠㅠ

이유가 뭘까요

#include <iostream>
#include <vector>
using namespace std;


//print dp array
void PrintDp(vector<vector<int>>& vectorArray,int n)
{
	for (int i = 1; i <= 2; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << vectorArray[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n" << endl;
}


int maximuValue = 0;

// now : Present index in vec array
//n : last number in vec array
int Dp(int now, int n, vector<int>& vec, vector<vector<int>>& dp, int drink)
{
	// if now is upper than n, do not check anymore
	if (now < n)
	{
		if (dp[drink][now] != -1)
			return dp[drink][now];
		else
		{
			if (drink == 1)
			{
				if ((vec[now] + Dp(now + 1, n, vec, dp, drink + 1)) > (vec[now] + Dp(now + 2, n, vec, dp, 1)))
				{
					dp[drink][now] = vec[now] + Dp(now + 1, n, vec, dp, drink + 1);
					if (dp[drink][now] > maximuValue)
						maximuValue = dp[drink][now];
					return dp[drink][now];
				}
				else
				{
					dp[drink][now] = vec[now] + Dp(now + 2, n, vec, dp, 1);
					if (dp[drink][now] > maximuValue)
						maximuValue = dp[drink][now];
					return dp[drink][now];
				}
					
			}
			else
			{
				dp[drink][now] = vec[now] + Dp(now + 2, n, vec, dp, 1);
				if (dp[drink][now] > maximuValue)
					maximuValue = dp[drink][now];
				return dp[drink][now];
			}
		}
	}
	else
		return 0;

	
}


int main()
{
	// #1 Initialization
	int n;
	cin >> n;


	vector<int> vec;
	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		vec.push_back(temp);
	}


	//a vector for memorizing
	vector<vector<int>> memo(3,vector<int>(n,-1));
	Dp(0, n, vec, memo,1);
	Dp(1, n, vec, memo, 1);

	cout << maximuValue << endl;

	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾을 수 없어요 ㅠㅠ 맞은 것 같지만...

tddhot2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말