4468 . LCS練習 (Hard Version)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

ある雨の日に、私と君と。
音楽のみなそこに眠る、夢と想像の世界

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

39.4% (13/33)

Tags

High DP

Description

三子題的輸入輸出要求皆不同，請看清楚題目再Submit

LCS(Longest Common Subsequence)，最長共同子序列

顧名思義，給你兩個長度為 $N$ 的數字序列$A, B$，且 $A$ 與 $B$ 皆為 $1$ ~ $N$ 的排列(Permutation)

找出他們的LCS長度

Constraints:

$N \leq 10^5$

Input Format

$N$

$A$

$B$

Output Format

LCS長度

Sample Input 1

2
1 2
2 1

Sample Output 1

1

Sample Input 2

4
1 2 3 4
1 3 2 4

Sample Output 2

3

Hints

子序列(Subsequence) 不一定要連續，但順序不能交換

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536
1 1000 250000 250000 65536
2 1000 250000 250000 65536
3 1000 250000 250000 65536
4 1000 250000 250000 65536
5 1000 250000 250000 65536
6 1000 250000 250000 65536
7 1000 250000 250000 65536
8 1000 250000 250000 65536
9 1000 250000 250000 65536
Submit
Back to Top