JLIS 문제 질문드립니다.

  • sclee1
    sclee1

    JLIS 문제를 푸는데 왜 오답이 나오는지 모르겠습니다.

    저 같은 경우는 seq를 이차원 배열로 놓고, 각각의 행을 가르키는 index를 두개로 설정합니다. (startA와 startB)

    그리고 조건을 만족할때마다 재귀적으로 호출해서 문제를 풀고 있는데..

    제가 구해놓은 모든 케이스는 정답인데..오답이 나오네요..

    혹시 문제점 알려주실수 있으실까요?

    /**
* JLIS
*
* @author Seungchul Lee
* @solved 2016. 08. 22
*
* http://algospot.com/judge/problem/read/JLIS
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,n) for(int i=0;i<n;++i)
#define INF 987654321

namespace JLIS {
    long long seq[101][101];
    int cache[101][101];
    int n;
    int m;

    int jlis(int startA,int startB,long long val) {

        int &ret = cache[startA+1][startB+1];
        if (ret != -1)
            return ret;

        ret = 1;

        for (int nextA = startA+1; nextA < n; ++nextA) {
            if (val < seq[0][nextA]) {
                ret = max(jlis(nextA, startB,seq[0][nextA])+1,ret);
            }
        }


        for (int nextB = startB+1; nextB < m; ++nextB) {

            if (val < seq[1][nextB]) {
                ret = max(jlis(startA, nextB,seq[1][nextB])+1, ret);
            }
        }

        return ret;
    }

    int do_main(int argc, const char *argv[]) {
        freopen("input.txt", "r", stdin);
        int TC;
        int cnt = 0;
        cin >> TC;

        while (TC--) {
            cin >> n;
            cin >> m;
            memset(cache, -1, sizeof(cache));

            FOR(i, n) {
                cin >> seq[0][i];
            }

            FOR(i, m) {
                cin >> seq[1][i];
            }

            int ans = jlis(-1, -1, -INF);



            cout << ans-1 << endl;
        }

        return 0;
    }
}

#ifndef DRIVER

int main(int argc, const char *argv[]) {
    return JLIS::do_main(argc, argv);
}

#endif

    7년 전
0개의 댓글이 있습니다.

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