[algospot] JLIS

문제링크 입니다

[JLIS] 문제

합친 최대 증가 부분 수열 찾기.

입력 값은 다음과 같습니다

12
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30
3 3
1 9 4
3 4 7
1 1
100
100
5 5
2 7 7 7 1
5 9 3 6 3
5 5
3 4 5 7 2
6 4 8 9 1
1 2
4
4 7
1 1
1
1
3 5
1 1 1
2 2 2 2 2
5 5
3 4 5 7 2
6 4 8 9 1
2 3
-2147483648 -2147483648
-2147483648 -2147483648 -2147483648

출력값은 다음과 같습니다. (사람들 데이터 추가)

#1 5
#2 6
#3 5
#4 5
#5 1
#6 4
#7 7
#8 2
#9 1
#10 2
#11 7
#12 1

전체 코드는 다음과 같습니다.

//
//  JLIS.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/21.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <limits>
using namespace std;

ifstream fin("JLIS.txt");
int cache[101][101];
int sequence1[101], sequence2[101];
int num1, num2;
const long long NEGINF = numeric_limits<long long>::min();

int LIS(int a, int b){
    int &ret = cache[a+1][b+1];
    if(ret != -1) return ret;
    ret = 0;
    long long A = (a==-1 ? NEGINF : sequence1[a]);
    long long B = (b==-1 ? NEGINF : sequence2[b]);
    long long maxElement = max(A,B);
    for(int i = a + 1; i < num1; ++i){
        if(maxElement < sequence1[i])
            ret = max(ret, LIS(i,b) + 1);
    }
    for(int i = b + 1; i < num2; ++i){
        if(maxElement < sequence2[i])
            ret = max(ret, LIS(a,i) + 1);
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        fin >> num1;
        fin >> num2;
        memset(cache,-1,sizeof(cache));
        memset(sequence1,-1,sizeof(sequence1));
        memset(sequence2,-1,sizeof(sequence2));
        for(int j=0; j< num1; j++){
            fin >> sequence1[j];
        }
        for(int k=0; k<num2; k++){
            fin >> sequence2[k];
        }
        cout << LIS(-1,-1) << endl;
    }
    return 0;
}