PKU 2181. Jumping Cows. [판정:AC]

정말 간만에 문제를 푼다는 느낌을 제대로 받는구만 ㅋㅋ


그리고 들보자식이 어느정도 사기(?)를 치고 있었다는 것도 알게 되었고//

최근에 올라온 [소점프 ac get] 글은
문제에 나온 예시만 돌려도 답을 얻을 수 없으니까
가급적 빠른 시일 내에 수정하도록 -_-;

// PKU 2181. Jumping Cows

#include 
using namespace std;

int s[150000];
int indexbound;

int calc( int start, int end, int isreverse )
{
	int i;
	int temp;
	int max, maxindex;
	int min, minindex;
	int result = 0;

	max = min = s[start];
	maxindex = minindex = start;
	for( i = start; i <= end; i++ )
	{
		if( max < s[i] )
		{
			max = s[i];
			maxindex = i;
		}
		if( min > s[i] )
		{
			min = s[i];
			minindex = i;
		}
	}

	if( start > end ) { return 0; }

	if( maxindex > minindex && !isreverse )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex, end, 0 );
	}
	else if( maxindex < minindex && !isreverse )
	{
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex+1, minindex-1, 1 );
		result += calc( minindex+1, end, 0 );
		result += max - min;
	}
	else if( maxindex > minindex && isreverse )
	{
		result += calc( start, minindex-1, 1 );
		result += calc( minindex+1, maxindex-1, 0 );
		result += calc( maxindex+1, end, 1 );
		result += max - min;
	}
	else if( maxindex < minindex && isreverse )
	{
		result += calc( start, maxindex, 1 );
		result += calc( maxindex+1, end, 1 );
	}
	else if( maxindex == minindex )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
	}

	return result;
}

int main()
{
	int p;
	int i;
	int height;

	scanf( "%d", &p );

	for( i = 0; i < p; i++ )
	{
		scanf( "%d", &s[i] );
	}

	if( p == 1 )
	{
		printf( "%d\n", s[0] );
	}
	else
	{
		height = calc( 0, p-1, 0 );
		
		// correction
		if( indexbound == 0 )
		{
			height += s[0];
		}
		else
		{
			int i;
			int max, maxindex;
			int min, minindex;

			max = min = s[indexbound];
			maxindex = minindex = indexbound;
			for( i = indexbound; i < p; i++ )
			{
				if( max < s[i] )
				{
					max = s[i];
					maxindex = i;
				}
				if( min > s[i] )
				{
					min = s[i];
					minindex = i;
				}
			}

			if( maxindex == p-1 )
			{
				height += max;
			}
			else
			{
				height += min;
			}
		}

		printf( "%d\n", height );
	}
	
	return 0;
}

풀이를 쓰다가,
내가 만들었던 예시에서 안맞는 부분이 발생하여

일단 풀이는 중단하고 코드만 올려놓았음//

그럼에도 AC가 나온건
아마 pku 서버 내의 테스트케이스를 모두 통과했기 때문이겠지 -_-;;