티스토리 뷰
https://algospot.com/judge/problem/read/JLIS
algospot.com :: JLIS
합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로
algospot.com
jlis(indexA,indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll NEGINF=numeric_limits<ll>::min();
int n,m,A[100],B[100];
int cache[101][101];
int jlis(int indexA,int indexB)
{
int &ret=cache[indexA+1][indexB+1];
if(ret!=-1) return ret;
ret=2;
ll a=(indexA==-1?NEGINF:A[indexA]);
ll b=(indexB==-1?NEGINF:B[indexB]);
ll maxElement=max(a,b);
for(int nextA=indexA+1;nextA<n;nextA++)
if(maxElement<A[nextA])
ret=max(ret,jlis(nextA,indexB)+1);
for(int nextB=indexB+1;nextB<m;nextB++)
if(maxElement<B[nextB])
ret=max(ret,jlis(indexA,nextB)+1);
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&A[i]);
for(int i=0;i<m;i++)
scanf("%d",&B[i]);
memset(cache,-1,sizeof(cache));
printf("%d\n",jlis(-1,-1)-2);
}
return 0;
}