글 읽기 - 틀렸다고 나옵니다.

tpfpske 5년 전 0

S1 < S2 ... < Sk > ... > Sn

의 입력받은 수열에서

1부터 k-1까지의 수열과 k+1부터 n까지의 수열로 각각 나눠서 계산한 뒤 기준점 수열의 길이인 1을 더해서 값을 구했습니다.

생각나거나 다른 질문들이 가지고 있는 몇 몇 예제는 통과하는 것 같은데 틀리다고 나옵니다.

// parm : 수열의 길이, 수열포인터, 기준값
int GetMaxLen(int N, int* score, int limit) : S1 < ... < S(k-1) 수열의 최대 길이
int GetMinLen(int N, int* score, int limit) : S(k+1) > ... > Sn 수열의 최대 길이

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

int GetMaxLen(int N, int* score, int limit)
{
    if (N < 1)
        return 0;
    int dp[N + 1];
    int max_len = 1;

    for(int i = 1; i <= N; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            if (dp[j] != 0 
             && score[j - 1] < score[i - 1]
             && score[i - 1] < limit)
                dp[i] = max(dp[i], dp[j] + 1);
        max_len = max(max_len, dp[i]);
    }

    return max_len;
}

int GetMinLen(int N, int* score, int limit)
{
    if (N < 1)
        return 0;
    int dp[N + 1];
    int max_len = 1;

    for(int i = 1; i <= N; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            if (dp[j] != 0 
             && score[j - 1] > score[i - 1]
             && score[i - 1] < limit)
                dp[i] = max(dp[i], dp[j] + 1);
        max_len = max(max_len, dp[i]);
    }

    return max_len;
}

int Answer(int N, int* score)
{

    int max_len = 0;
    for (int i = 1; i <= N; i++)
        max_len = max(max_len, GetMaxLen(i - 1, score, *(score+i))
        + GetMinLen(N - i, (score + i), *(score + i)) + 1);

    return max_len;
}

void TEST(int param,int* score, int expected)
{
    int ans = Answer(param, score);
    if (ans == expected) 
        printf("Success!\n");
    else
        printf("Failed..\nexpected : %d\nAnswer   : %d\n", expected, ans);
}

void TESTCASE()
{
    int score_size;

/*
    int temp[5] = { 1, 2, 3, 5, 4 };
    cout << "asd";
    cout << GetMaxLen(5, temp, 6) << endl;
    cout << GetMinLen(5, temp, 0) << endl;
    */

    score_size = 10; 
    int score1[score_size] = { 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 };
    TEST(score_size, score1, 7);

    score_size = 1;
    int score4[score_size] = { 50 };
    TEST(score_size, score4, 1);

    score_size = 2;
    int score5[score_size] = { 40, 50 };
    TEST(score_size, score5, 2);

    score_size = 2;
    int score6[score_size] = { 50, 40 };
    TEST(score_size, score6, 2);

    score_size = 5;
    int score7[score_size] = { 1, 5, 4, 2, 3 };
    TEST(score_size, score7, 4);

    score_size = 17;
    int score8[score_size] = { 7, 2, 1, 1, 5, 2, 2, 3, 2, 3, 1, 2, 4, 5, 1, 2, 4 };
    TEST(score_size, score8, 6);

    score_size = 7;
    int score9[score_size] = { 1, 2, 4, 3, 2, 4, 1 };
    TEST(score_size, score9, 6);

    score_size = 7;
    int score10[score_size] = { 1, 4, 3, 2, 1, 5, 6 };
    TEST(score_size, score10, 5);
}

int main()
{
#if 0
    TESTCASE();
#else
    int T, N;
    //scanf("%d", &T);
    //for (int i = 0; i< T; i++)
    {
        scanf("%d", &N);
        int score[N];
        for (int j = 0; j < N; j++) scanf("%d", &score[j]);
        printf("%d\n", Answer(N, score));
    }
#endif

    return 0;
}

luniro 5년 전 0

반례 드립니다

입력:
6
5 1 6 2 6 2 1

출력:
4

정답:
5

luniro 5년 전 0

또 다른 반례입니다

입력:
9
5 1 6 2 7 3 7 2 1

출력:
7

정답:
6

cakeme 4년 전 4

luniro님 첫 반례

5 1 6 2 6 2 1

수열 크기 6이 아니라 7으로넣으세요...

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

문제

문제

출처

ICPC

틀렸다고 나옵니다.

tpfpske 5년 전 0

luniro 5년 전 0

luniro 5년 전 0

cakeme 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말