CFCF2165D.Path Split

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$ 。

你需要将 $a$ 划分为若干个子序列 $b_1, b_2, \ldots, b_k$ ，使得满足以下条件：

$a$ 中的每个元素恰好属于一个 $b_i$ 。
对于每个序列 $b_i$ ，设其元素为 $b_{i,1}, b_{i,2}, \ldots, b_{i,p_i}$ 。对于每一个 $1 \leq j < p_i$ ，都需满足 $|b_{i,j} - b_{i,j+1}| = 1$ 。

请计算 $a$ 至少需要划分成几个子序列。

注：“子序列”是指通过从原序列 $a$ 中删除若干（可能为零或全部）元素且不改变其余元素的相对顺序后所得的一个序列。

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

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

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1\leq a_i\leq 2n$ ），表示序列 $a$ 。

保证所有测试用例的 $n$ 之和不超过 $10^6$ 。

对于每个测试用例，输出一个整数，表示将 $a$ 划分成最少多少个子序列。

输入#1

7
1
1
1
2
8
11 13 10 11 11 11 13 10
6
8 8 6 7 7 7
3
5 1 3
10
11 14 14 13 12 14 12 10 14 12
1
2

输出#1

在第一个测试用例中，可以将 $a$ 划分为子序列 $[1]$ 。显然无法划分得更少，因此答案是 $1$ 。

在第三个测试用例中，可以将 $a$ 划分为子序列 $[11,10,11,10]$ 、 $[13]$ 、 $[11]$ 、 $[11]$ 、 $[13]$ 。要注意 $[11,10,11,11,11,10]$ 不是一个有效子序列，因为 $|11-11|=0\neq1$ 。

由 ChatGPT 5 翻译