# [Platinum III] Double Deck [문제 링크](https://www.acmicpc.net/problem/32552) ## 문제 설명 <p>You are playing a new card game. In the game you have two decks of cards each consisting of $N \cdot K$ cards labeled with an integer from $1$ to $N$, inclusive. Also, each type of card appears precisely $K$ times in each deck.</p> <p>The rules of the game are simple. You shuffle both decks and place them face up in front of you, so at each point in time you see the top card in each deck. If the top cards are the same you can take them both and get one point. Otherwise you must discard either card. Your goal is to get as many points as possible.</p> <p>You have just finished playing a round of this game and you want to know what the maximum score was, knowing the layout of both decks.</p> ## 입력 <p>The first line of the input contains two integers $N$ and $K$ ($1 \leq N \leq 10^4, 1 \leq K \leq 15$). The second and third line of the input each contain $N \cdot K$ integers $x_i$ ($1 \leq x_i \leq N$), describing the layout of the decks. The first number $x_1$ is the topmost card in the deck, $x_2$ is the second, and so on.</p> <p>No integer in the second line and third line is repeated more than $K$ times per line.</p> ## 출력 <p>Print a single integer, the maximum possible score.</p> ## 풀이 [전깃줄](https://www.acmicpc.net/problem/2568) 문제와 같은데 한 정점에서 여러 개씩 나갈 수 있다는 차이가 있다. 이를 출발 지점 오름차순, 도착 지점 내림차순으로 정렬한 후 LIS를 하면 똑같이 최대 매칭 수가 나온다. ``` c++ #include<bits/stdc++.h> using namespace std; vector<int> arr; vector<vector<int>> idxs(10'001); int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; // A와 B 위아래 위치 변경 for(int i=0;i<n*k;i++) { int a; cin >> a; idxs[a].push_back(i); } for(int i=0;i<n*k;i++) { int b; cin >> b; for(int j=k-1;j>=0;j--) arr.push_back(idxs[b][j]); } vector<int> lis; for(int e:arr) { if(lis.empty() || lis.back()<e) lis.push_back(e); else lis[lower_bound(lis.begin(), lis.end(), e)-lis.begin()]=e; } cout << lis.size(); } ```