글 읽기 - 가장 긴 바이토닉 부분 수열 반례를 찾아주세요 ㅠㅠ

dpdpwl75 5년 전 0

게시판 반례는 모두 정답으로 나옵니다.. 혹시 반례가 있을까요?

dp[i][0] 은 증가하는 부분수열

dp[i][1] 은 뒷배열이 앞보다 작을시에 최대값으로 갱신 하는 방식으로 해봤는데..

이런식으로 하는게 잘못됐으니 틀렸겠지요.. 반례가 궁금합니다.

#include<iostream>
using namespace std;

int N,R,arr[1001],dp[1001][2];

int main()
{
	scanf("%d",&N);
	for(int i = 1; i<=N; i++)
		scanf("%d",&arr[i]);

	for(int i = 1; i<=N; i++)
	{
		for(int j = 1; j<i; j++)
			if(arr[i]>arr[j])
				dp[i][0] = max(dp[i][0], dp[j][0]);
			else if(arr[i]<arr[j])
				dp[i][1] = max(dp[j][0], dp[j][1]);
		dp[i][0] += 1;
		dp[i][1] += 1;
		R = max(R,max(dp[i][0],dp[i][1]));
	}
	printf("%d",R);
}

kimsy96 5년 전 0

푸셨네요

dpdpwl75 5년 전 0

정답은 다른방법으로 푼것입니다 ㅜㅜ

정방향 + 역방향 -1 으로요..

위에 코드의 반례가 궁금합니다.

djm03178 5년 전 0

7
1 2 4 3 2 4 1

마지막 1에 대한 값을 계산할 때 6번째에 있는 4 때문에 값이 덮어써집니다.

dpdpwl75 5년 전 0

와 정말 감사합니다!!!

dpdpwl75 5년 전 0

else if 문에 max 한줄 추가하니 맞습니다가 나오는군요..

			else if(arr[i]<arr[j])
				dp[i][1] = max(dp[i][1], max(dp[j][0], dp[j][1]));

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

문제

문제

출처

ICPC

가장 긴 바이토닉 부분 수열 반례를 찾아주세요 ㅠㅠ

dpdpwl75 5년 전 0

kimsy96 5년 전 0

dpdpwl75 5년 전 0

djm03178 5년 전 0

dpdpwl75 5년 전 0

dpdpwl75 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말