글 읽기 - 반례 전부 통과했는데 시작하자마자 틀렸습니다가 뜹니다.

mk970205 3년 전 0

바이토닉 문제입니다.

i를 끝으로 하는 증가부분수열, i를 시작으로 하는 감소부분수열을 구했습니다.

그 후 각 두 함수의 최대가 되는 부분을 찾아서 결과로 반환했습니다.

반례에 나온 것들은 다 맞는데 퍼센트도 안뜨고 바로 틀렸다고 나옵니다.

해결 부탁드립니다.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
vector<int> cache_asc(1010, -1);
vector<int> cache_desc(1010, -1);
vector<int> seq(1010, -1);
int N;

// i가 끝점인 증가부분수열의 최대 길이
int dp_asc(int i) {
    int& ret = cache_asc[i];
    if(ret != -1) return ret;
    
    ret = 1;
    for(int j = 0; j < i; j++) {
        if(seq[i] < seq[j]) {
            ret = max(ret, 1 + dp_asc(j));
        }
    }
    return ret;
}

// i가 시작점인 감소부분수열의 최대 길이
int dp_desc(int i) {
    int& ret = cache_desc[i];
    if(ret != -1) return ret;
    
    ret = 1;
    for(int j = i + 1; j < N; j++) {
        if(seq[i] > seq[j]) {
            ret = max(ret, 1 + dp_desc(j));
        }
    }
    return ret;
}

int solve() {
    int answer = 0;
    for(int i = 0; i < N; i++) {
        answer = max(answer, dp_asc(i) + dp_desc(i) - 1);
    }
    
    return answer;
}

int main() {
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;    
    for(int n = 0; n < N; n++) {
        cin >> seq[n];
    }
    cout << solve() << '\n';
}

ghghgh777 3년 전 1

예제 넣으면 5 나옵니다.

잘못된 부분은 dp_asc() 에 있는 부등호 방향입니다.

mk970205 3년 전 0

@ghghgh777 앗 감사합니다 다른 PC에서 푼 것을 옮겨적는 과정에서 오타가 났었나보네요

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

문제

문제

출처

ICPC

반례 전부 통과했는데 시작하자마자 틀렸습니다가 뜹니다.

mk970205 3년 전 0

ghghgh777 3년 전 1

mk970205 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말