Algorithm/알고스팟
algospot - jlis
jhg0406
2020. 2. 2. 18:38
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
//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";
}
}
|
cs |
https://www.algospot.com/judge/problem/read/JLIS
algospot.com :: JLIS
합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. 두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부
www.algospot.com
JLIS
DP문제
cache[A][B] : 첫번째 수열 A부터 시작하는 부분수열과 두번쨰 수열 B부터 시작하는 부분수열중 가장 큰 JLIS의 길이를 저장합니다.
