KLIS가 계속 오답이 뜹니다.

  • junyoung2
    junyoung2

    오버플로를 막기위해서countLis가 5000000000 초과할 때 countLis가 5000000000를 반환하도록 만들어도(countLis는 long long을 반환합니다) 오답이 나옵니다. k가 무슨 입력이 들어와도 처리할 수 있게 k도 long long으로 받았습니다.
    아래에 소스코드를 첨부합니다.

    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    int seq[500];
    int size;
    long long skip;
    long long k;
    int cache[501];
    long long cache2[501];
    vector<int> result;
    
    int lis(int x)
    {
        int& ret = cache[x];
        if(ret != -1)
            return ret;
    
        ret = 1;
    
        for(int i = x + 1; i < size; i++)
        {
            if(seq[i] > seq[x])
            {
                ret = max(ret, 1 + lis(i));
            }
        }
    
        return ret;
    }
    
    int lisSize()
    {
        int ret = 0;
        for(int i = 0; i < size; i++)
        {
            ret = max(ret, lis(i));
        }
    
        return ret;
    }
    
    long long countLis(int x)
    {
        long long& ret = cache2[x];
        if(ret != -1)
            return ret;
        ret = 0;
        if(lis(x) == 1)
            return ret = 1;
        for(int i = x + 1; i < size; i++)
        {
            if((lis(i) == lis(x) - 1) && (seq[x] < seq[i]))
            {
                ret += countLis(i);
                if(ret > 5000000000)
                    ret = 5000000000;
            }
        }
    
        return ret;
    }
    
    void getK(int prev, int len, int x)
    {
        if(len == 0)
            return;
        vector<int> search;
        int index;
        if(skip == k - 1)
        {
            for(int i = 0; i < size; i++)
            {
                if(lis(i) == len)
                search.push_back(seq[i]);
            }   
    
            sort(search.begin(), search.end());
    
            for(int i = 0; i < search.size(); i++)
            {
                for(int j = 0; j < size; j++)
                {
                    if(search[i] == seq[j])
                    index = j;
                }
                if(countLis(index) <= skip)
                skip -= countLis(index);
                else
                {
                    result.push_back(seq[index]);
                    getK(seq[index], len - 1, index + 1);
                    return;
                }
            }
        }
    
        for(int i = x; i < size; i++)
        {
            if(lis(i) == len && seq[i] > prev)
            search.push_back(seq[i]);
        }
    
        sort(search.begin(), search.end());
    
        for(int i = 0; i < search.size(); i++)
        {
            for(int j = x; j < size; j++)
            {
                if(search[i] == seq[j])
                index = j;
            }
            if(countLis(index) <= skip)
                skip -= countLis(index);
            else
            {
                result.push_back(seq[index]);
                getK(seq[index], len - 1, index + 1);
                return;
            }
        }
    }
    
    
    int main()
    {
        int cases;
        cin >> cases;
        while(cases--)
        {
            memset(cache, -1, sizeof(cache));
            for(int i = 0; i < 501; i++)
            {
                cache2[i] = -1;
            }
            cin >> size >> k;
            skip = k - 1;
            for(int i = 0; i < size; i++)
                cin >> seq[i];
            getK(0, lisSize(), 0);
            cout << lisSize() << endl;
            for(int i = 0; i < result.size(); i++)
                cout << result[i] << " ";
            cout << endl;
            result.clear();
        }
    
        return 0;
    }
    

    3달 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.