解题思路

本题是在“最长上升子序列（LIS）”基础上的扩展：在所有长度为全局最长的上升子序列中，最大化其中属于集合 $Y$ 的元素个数。 采用经典的 $O(n^2)$ 动态规划 思路，并在状态中同时维护两项：

• len[i]：以第 $i$ 颗宝石结尾的 LIS 的最大长度；
• cnt[i]：在所有达到 len[i] 的方案中，包含稀有宝石（在 $Y$ 中）个数的最大值。

转移（对每个 $i$，枚举所有 $j<i$ 且 $C_j<C_i$）：

题目内容

在魔法世界中，探险家发现了一排 $n$ 颗魔法宝石，每颗宝石都有独特的魔力值。一条宝石链是指从这排宝石中选取若干题(可以不选成全选)，保持它们原有的相对顺序排列。如果宝石礴的魔力值从左则右严格递增，则称为一条上升宝石链。所有上升宝石链中，长度最长的称为量长上升宝石链。

魔法学院特别关注某然贴有宝石，定义了一个稀有宝石集合 $Y$ ，一条宝石链与集合 $Y$ 的契合康星指这条宝石链中包含的稀有宝石的数量。

约定一排 $n$ 颗宝石的魔力值序列 $C$ 以及稀有宝石集合 $Y$ ，请计算在所有最长上升宝石链中，与集合 $Y$ 的最大契合度是多少(即最多包含多少颗稀有宝石)，输出这个最大契合度。

输入描述

第一行一个正整数 $n$ ,表示宝石的数量。

第二行是 $n$ 个用空格隔开的正整数$C_1,C_,…,C_n$ ，其中 $C_i$ 表示第 $i$ 颗宝石的魔力值。

第三行是一个正整数 $k$ ,表示稀有宝石集合 $Y$ 的大小。

第四行是 $k$ 个用空格隔开的正整数 $y_1,y_2,...,y_k$ ,表示稀有宝石集合 $Y$ 中的 $k$ 颗宝石的魔为值.

$1 ≤ n,k ≤ 2000,1 ≤ c_i,y_i ≤ 10^9$

输出描述

一个整数，表示最长上升宝石链与稀有宝石集合 $Y$ 的最大契合度。

样例1

输入

5
10 20 30 15 25
3
10 15 30

输出

2