글 읽기 - 바이토닉 부분수열 게시판 반례 다 돌려봤습니다.

gkfkagkfka12 5년 전 0

가장 긴 증가하는 부분 수열 + 해당 수열이 끝난 인덱스부터 가장 긴 감소하는 부분 수열 -1로 풀었고

예제를 비롯해 게시판에 있는 모든 반례까지 맞는데 어디가 틀린지 모르겠습니다.

찾아주시면 감사하겠습니다.

#include <cstdio>
#include <algorithm>

int a[1001],d[1001],n,max,m;

int main(void)
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        d[i]=1;
    }


    max=d[1];
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(a[i]>a[j] && d[j]+1>d[i])
                d[i] = d[j]+1;
        }
        if(d[i]>max){
            max=d[i];
            m=i;
        } 
    }

    int temp = max;
    for(int i=m; i<=n; i++) d[i]=1;
    max=d[m];
    for(int i=m+1; i<=n; i++){
        for(int j=m; j<i; j++){
            if(a[i]<a[j] && d[j]+1>d[i])
                d[i] = d[j]+1;
        }
        if(d[i]>max) max=d[i];
    }

    printf("%d\n", max+temp-1);

    return 0;
}

djm03178 5년 전 4

가장 긴 증가하는 부분 수열의 끝에서 시작하는 것이 최적일까요?

아래 예시에서 가장 긴 증가하는 부분 수열은 1 2 3이지만, 3에서부터 다시 감소하는 부분 수열을 구해도 총 길이가 더 늘어나지 못합니다.

하지만 증가 부분을 1 5로 잡으면, 감소 부분은 5 4 3으로 잡을 수 있어 총 길이를 4로 만들 수 있습니다.

5
1 5 4 2 3

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

문제

문제

출처

ICPC

바이토닉 부분수열 게시판 반례 다 돌려봤습니다.

gkfkagkfka12 5년 전 0

djm03178 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말