글 읽기 - 바이토닉 수열 틀린 테스트케이스를 못 찾겠네요 ㅠ

dkdsla12 7년 전 0

시간초과도 아니고 그냥 틀렸습니다 뜨는데..

어디가 틀린걸까요??..ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX(a,b) (a>b?a:b)
int arr[1001], n;
int cache[1001][2];
int dp(int v, int o) {
	int &ret = cache[v][o];
	if (ret != 0) return cache[v][o];
	if (o == 1)
		for (int i = v + 1; i < n; i++)
			if (arr[v] < arr[i])
				ret = MAX(ret, dp(i, o));
	if (ret == 0 || o == 0)
		for (int i = v + 1; i < n; i++)
			if (arr[v] > arr[i])
				ret = MAX(ret, dp(i, 0));
	ret++;
	return ret;
}
int main() {
	scanf("%d", &n);
	memset(cache, 0, sizeof(int) * 1001 * 2);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	int ret = 0;//1이면 증가수열 0이면 감소수열
	for (int i = 0; i < n; i++) {
		ret = MAX(ret, dp(i, 1));
		ret = MAX(ret, dp(i, 0));
	}
	printf("%d", ret);
}

gkdlmc77 7년 전 1

17
7 2 1 1 5 2 2 3 2 3 1 2 4 5 1 2 4

혹시 이 경우 되나요?
정답은 6 입니다.

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

문제

문제

출처

ICPC

바이토닉 수열 틀린 테스트케이스를 못 찾겠네요 ㅠ

dkdsla12 7년 전 0

gkdlmc77 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말