algospot - jlis

//algospot - jlis
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<long long> v1;
vector<long long> v2;
vector<vector<int>> cache;
 
void init()
{
    cin >> N >> M;
    v1 = vector<long long>(N+1);
    v2 = vector<long long>(M+1);
    cache = vector<vector<int>>(N + 1, vector<int>(M+1, -1));
    for (int i = 1; i <= N; ++i)
        cin >> v1[i];
    for (int i = 1; i <= M; ++i)
        cin >> v2[i];
    v1[0] = v2[0] = -3333333333;
}
 
int dp(int idx1, int idx2)
{
    int &ret = cache[idx1][idx2];
    if (ret != -1)
        return ret;
    ret = 0;
    long long num = max(v1[idx1], v2[idx2]);
    for (int i = idx1 + 1; i <= N; ++i)
        if (num < v1[i])
            ret = max(ret, dp(i, idx2));
 
    for (int i = idx2 + 1; i <= M; ++i)
        if (num < v2[i])
            ret = max(ret, dp(idx1, i));
 
    ++ret;
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        int ans = dp(0, 0);
        cout << ans - 1 << "\n";
    }
}

 

 

 

 

 

https://www.algospot.com/judge/problem/read/JLIS

algospot.com :: JLIS

 

 

 

 

 

JLIS

DP문제

cache[A][B] : 첫번째 수열 A부터 시작하는 부분수열과 두번쨰 수열 B부터 시작하는 부분수열중 가장 큰 JLIS의 길이를 저장합니다.