글 읽기 - 바이토닉수열 반례를 모르겠습니다

jemin9312 5년 전 0

가장 긴 값을 찾아내서 d1배열에 저장, 그 값의 인덱스를 받아온 뒤 그 받아온 인덱스부터 끝까지 감소하는 수열의 최대값을 구해서 d2에 저장 후 d1과 d2를 모두 순회하며 d1+d2-1 의 최대값을 찾아냈는데... 틀렸다고 합니다 어디서 틀린걸까요?

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

int d1[1001];
int d2[1001];
int num[1001];

int cal(int a) {
	int mx1 = 0;
	int mx2 = 0;
	int max_idx;


	for (int i = 0; i < a; i++) {
		d1[i] = 1;
		for (int j = 0; j < i; j++) {
			if (num[j] < num[i] && d1[j] + 1> d1[i])
				d1[i] = d1[j] + 1;
		}
	}
	for (int i = 0; i < a; i++) {
		if (mx1 < d1[i]) {
			mx1 = d1[i];
			max_idx = i;
		}
	}

	for (int i = max_idx; i < a; i++) {
		d2[i] = 1;
		for (int j = max_idx; j < i; j++) {
			if (num[j] > num[i] && d2[j] + 1> d2[i])
				d2[i] = d2[j] + 1;
		}
	}

	for (int i = 0; i < a; i++) {
		for(int j = 0;j<a;j++)
		if (mx2 < d1[i] + d2[j] - 1)
			mx2 = d1[i] + d2[j] - 1;
	}


	return mx2;
}

int main() {

	int a;


	scanf("%d", &a);

	for (int i = 0; i < a; i++)
	{
		int x;
		scanf("%d", &x);
		num[i] = x;
	}


	printf("%d", cal(a));
}

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

문제

문제

출처

ICPC

바이토닉수열 반례를 모르겠습니다

jemin9312 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말