解题思路

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

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

题目内容

在一个考古遗址中，勘探队沿直线钻取了一排 $n$ 个地层样本，按钻取顺序编号为 $1$ 到 $n$ ，每个样本有一个深度值。地质学家希望从这排样本中按原有顺序选出一个子序列，使得深度值严格递增，以还原地壳持续沉降的过程。我们称这样的子序列为一条上升轨迹，其中最长的上升轨迹称为最长轨迹。

同时，勘探队发现在某些特定深度处存在罕见的标志性化石，这些深度构成一个关键深度集合。一条上升轨迹的关键含量定义为其中深度值属于该集合的样本个数。

请计算：在所有最长轨迹中，关键含量的最大值是多少。

规定样本数量 $n$ 和关键深度集合的大小 $k$ 均不超过 $2000$ ，每个深度值均为不超过 $10^9$ 的正整数。