No.3782 Synchronized Subsequences
タグ : / 解いたユーザー数 9
作問者 :
Note
The time limit for this problem is $3$ seconds.
Problem Statement
You are given a positive integer $N$ and permutations $P=(P_1,P_2,\cdots,P_N)$ and $Q=(Q_1,Q_2,\cdots,Q_N)$ of $(1,2,\cdots ,N)$. Find the maximum integer $k$ such that there exists a pair of $2$ integer sequences of length $k$, $(A,B)=((A_1,A_2,\cdots ,A_k),(B_1,B_2,\cdots ,B_k))$, satisfying the following conditions. (It can be proved that at least one such pair $(A,B)$ exists.)
- $A$ is a (not necessarily contiguous) subsequence of $P$, and $B$ is a (not necessarily contiguous) subsequence of $Q$.
- For each integer $i$ satisfying $1\le i< k $, $(A_{i+1}-A_i)(B_{i+1}-B_i) > 0$.
Solve $T$ test cases.
Constraints
- $1\le T\le 1000$
- $1 \le N \le 1000$
- $(P_1,P_2,\cdots ,P_N)$ and $(Q_1,Q_2,\cdots ,Q_N)$ are each a permutation of $(1,2,\cdots ,N)$
- The sum of $N$ over the $T$ test cases is at most $1000$
- All input values are integers
Input
The input is given in the following format, where $case_i$ denotes the $i$-th test case.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each test case is given in the following format.
$N$ $P_1\ P_2\ \cdots\ P_N$ $Q_1\ Q_2\ \cdots\ Q_N$
Output
Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.
Sample
Sample 1
Input
2 6 3 6 1 5 4 2 4 1 2 6 3 5 15 9 13 12 4 8 14 7 15 10 1 2 5 6 11 3 9 6 11 4 7 5 13 1 8 2 12 10 3 14 15
Output
4 11
For the $1$st test case, $A=(3,6,1,5),B=(4,6,3,5)$ satisfies the conditions. There is no $(A,B)$ of length $5$ or more satisfying the conditions, so the answer is $4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。