解题思路
本题是在“最长上升子序列（LIS）”基础上的扩展：在所有长度为全局最长的上升子序列中，最大化其中属于集合 Y 的元素个数。
采用经典的 O(n2) 动态规划 思路，并在状态中同时维护两项：
len[i]：以第 i 颗宝石结尾的 LIS 的最大长度；cnt[i]：在所有达到 len[i] 的方案中，包含稀有宝石（在 Y 中）个数的最大值。
转移（对每个 i，枚举所有 j<i 且 Cj<Ci）：
P4300.第1题-魔法宝石
题目内容
在魔法世界中，探险家发现了一排 n 颗魔法宝石，每颗宝石都有独特的魔力值。一条宝石链是指从这排宝石中选取若干题(可以不选成全选)，保持它们原有的相对顺序排列。如果宝石礴的魔力值从左则右严格递增，则称为一条上升宝石链。所有上升宝石链中，长度最长的称为量长上升宝石链。
魔法学院特别关注某然贴有宝石，定义了一个稀有宝石集合 Y ，一条宝石链与集合 Y 的契合康星指这条宝石链中包含的稀有宝石的数量。
约定一排 n 颗宝石的魔力值序列 C 以及稀有宝石集合 Y ，请计算在所有最长上升宝石链中，与集合 Y 的最大契合度是多少(即最多包含多少颗稀有宝石)，输出这个最大契合度。
输入描述
第一行一个正整数 n ,表示宝石的数量。
第二行是 n 个用空格隔开的正整数C1,C,…,Cn ，其中 Ci 表示第 i 颗宝石的魔力值。
第三行是一个正整数 k ,表示稀有宝石集合 Y 的大小。
第四行是 k 个用空格隔开的正整数 y1,y2,...,yk ,表示稀有宝石集合 Y 中的 k 颗宝石的魔为值.
1≤n,k≤2000,1≤ci,yi≤109
输出描述
一个整数，表示最长上升宝石链与稀有宝石集合 Y 的最大契合度。
样例1
输入
5
10 20 30 15 25
3
10 15 30
输出
2
