最长公共上升子序列 LCIS

题目描述

给定两个长度为 $N$ 的整数序列 $A$ 和 $B$。

如果某个序列同时是 $A$ 和 $B$ 的子序列，并且该序列中的元素严格递增，则称它为 $A$ 和 $B$ 的公共上升子序列。

请你求出 $A$ 和 $B$ 的最长公共上升子序列的长度。

这里“子序列”指从原序列中删除任意多个元素后，剩余元素保持原有相对顺序得到的序列。子序列不要求连续。

“严格递增”指后一个元素必须严格大于前一个元素。

输入格式

第一行一个整数 $N$，表示序列 $A$ 和 $B$ 的长度。

第二行包含 $N$ 个整数，表示序列 $A$。

第三行包含 $N$ 个整数，表示序列 $B$。

输出格式

输出一行一个整数，表示最长公共上升子序列的长度。

输入输出样例 #1

输入 #1

4
2 2 1 3
2 1 2 3

输出 #1

2

说明/提示

样例解释

序列 $A=[2,2,1,3]$，序列 $B=[2,1,2,3]$。

一个最长公共上升子序列是 $[1,3]$：

• 在 $A$ 中可取第 $3$ 个元素 $1$ 和第 $4$ 个元素 $3$；
• 在 $B$ 中可取第 $2$ 个元素 $1$ 和第 $4$ 个元素 $3$；
• 该子序列严格递增。

其长度为 $2$。此外，$[2,3]$ 也是长度为 $2$ 的公共上升子序列。

数据规模与约定

• $1 \le N \le 3000$
• $0 \le |A_i|, |B_i| \le 10^6$

序列中的每个整数绝对值不超过 $10^6$，可以为正数、负数或零。