ID : KLIS 질문입니다.

  • TLB_MISS
    TLB_MISS

    예제 입력이 잘 나오는 것으로 보아 overflow 문제인 거 같은데 도저히 감을 못잡겠습니다.. 문제 조건에 따라 MAX값 보다 signed 32-bit integer의 MAX값보다 높게 설정했고.. lis와 count는 책을 참고하여 작성했구요, KLIS를 구하는 함수는 저만의 방식으로 작성해보았습니다. 남의 code를 보고 문제를 찾는 것이 쉽지 않다는 것은 알지만 혹시 도움을 주실 수 있는 분이 있다면 간곡히 부탁드립니다. 감사합니다.

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const long long MAX = 2500000000;
    int n;
    long long k;
    int lisCache[501], S[500], pos[100000 + 1];
    long long countCache[501], countLIS[100000 + 1];
    vector<int> KLIS;
    
    // S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
    int lis(int start) {
        int& ret = lisCache[start + 1];
    
        if (ret != -1)
            return ret;
    
        // lis의 최소 길이는 1.
        ret = 1;
    
        for (int next = start + 1; next < n; ++next) {
            if (start == -1 || S[start] < S[next])
                ret = max(ret, lis(next) + 1);
        }
    
        return ret;
    }
    
    // S[start]에서 시작하는 LIS의 수를 반환.
    long long count(int start) {
        // base case : LIS의 길이가 1인 경우.
        if (lis(start) == 1)
            return 1;
    
        // memoization
        long long& ret = countCache[start + 1];
        if (ret != -1)
            return ret;
    
        ret = 0;
    
        for (int next = start + 1; next < n; ++next) {
            if ((start == -1 || S[start] < S[next]) && lis(start) == lis(next) + 1)
                ret = min<long long>(MAX, ret + count(next));
        }
        return ret;
    }
    
    void klis(int start, int lis_0) {
        int length = lis(start) - 1;
    
        fill(&countLIS[0], &countLIS[0] + 100000 + 1, 0);
    
        for (int i = start + 1; i < n; ++i) {
            if ((start == -1 || S[start] < S[i]) && lis(i) == length) {
                countLIS[S[i]] = count(i);
            }
        }
    
        int newStart = start + 1;
        for (int i = 1; i < 100001; ++i) {
            if (k <= countLIS[i]) {
                KLIS.push_back(i);
                newStart = pos[i];
                break;
            }
            k -= countLIS[i];
        }
    
        if (KLIS.size() == lis_0)
            return;
        klis(newStart, lis_0);
    }
    
    int main() {
        int T;
        cin >> T;
    
        for (int i = 0; i < T; ++i) {
            cin >> n >> k;
            for (int j = 0; j < n; ++j) {
                cin >> S[j];
                pos[S[j]] = j;
            }
            fill(&lisCache[0], &lisCache[0] + 501, -1);
            fill(&countCache[0], &countCache[0] + 501, -1);
    
            int lis_0 = lis(0);
            cout << lis_0 << endl;
            klis(-1, lis_0);
            for (int j = 0; j < KLIS.size() - 1; ++j) {
                cout << KLIS[j] << " ";
            }
            cout << KLIS[KLIS.size() - 1] << endl;
    
            KLIS.clear();
        }
    }
    

    4년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.