CF2124H.Longest Good Subsequence

如果一个长度为 $m$ 的数组 $b$ 满足以下条件，则称其为“好”的：

• 对于每个 $1 \leq i \leq m$，都有 $1 \leq b_i \leq i$。
• 存在一个长度为 $m$ 的排列 $p$，使得对于每个 $1 \leq i \leq m$，$b_i$ 是使得 $\min(p_{b_i}, p_{b_i+1}, \ldots, p_i)=p_i$ 成立的最小整数。

例如，数组 $[1,1,3,3,5]$ 是“好”的（排列 $p=[2,1,5,3,4]$ 满足第二个条件），但数组 $[1,1,2]$ 不是。

注意，空数组也被认为是“好”的。

给定一个长度为 $n$ 的数组 $a$，请你求出 $a$ 的最长“好”子序列的长度。

一个长度为 $m$ 的排列是由 $1$ 到 $m$ 的 $m$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$m=3$ 但数组中有 $4$）。

序列 $c$ 是序列 $d$ 的子序列，当且仅当 $c$ 可以通过从 $d$ 中删除若干（可能为零或全部）元素得到。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 15000$），表示数组 $a$ 的长度。

每组测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq n$），表示数组 $a$。

保证所有测试用例中 $n^2$ 的和不超过 $15000^2$。

对于每组测试用例，输出 $a$ 的最长“好”子序列的长度，每个结果占一行。

在第一个测试用例中，整个序列就是“好”的。

在第二个测试用例中，最长的“好”子序列是 $[1,2]$。

由 ChatGPT 4.1 翻译