글 읽기 - 95% 틀렸습니다

kep1er07 1년 전 0

11055 소스 코드에서 24번째 줄 부등호만 수정하여 제출하였습니다.

#include <iostream>

using namespace std;

int n;
int a[1004];
int ans;
int dp[1004];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    dp[0] = a[0];
    ans = a[0];
    for (int i = 1; i < n; i++)
    {
        dp[i] = a[i];
        for (int j = 0; j < i; j++)
        {
            if (a[j] > a[i])
            {
                dp[i] = max(dp[i], dp[j] + a[i]);
                if (dp[i] > ans)
                {
                    ans = dp[i];
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

azberjibiou 1년 전 0

21번 줄에서도 ans를 업데이트해주세요.

kep1er07 1년 전 0

11055에서는 해당 위치에서 ans를 업데이트하지 않아도 통과되는 이유가 뭘까요?

azberjibiou 1년 전 0

위의 케이스의 반례는 최대 감소 부분 수열이 길이가 1이고 배열의 첫번째 값이 아닌 경우입니다.

최대 감소 부분수열의 길이가 1이고 배열의 첫번째 값이 아닌 경우는 1 1 100 과 같은 경우가 있지만

최대 증가 부분수열의 길이가 1이기 위해서는 그 부분수열은 첫번째 값이어야 합니다.

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

문제

문제

출처

ICPC

95% 틀렸습니다

kep1er07 1년 전 0

azberjibiou 1년 전 0

kep1er07 1년 전 0

azberjibiou 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말