A16187. Block Sequence
编程题
普及/提高-
知识点
题目描述
给定一个由 $n$ 个正整数组成的序列 $a_1, a_2, \dots, a_n$。
你可以执行任意次操作。每次操作中，你**删除**序列中的一个元素。删除元素后，剩下的元素保持原来的相对顺序。
操作结束后，剩下的序列应满足以下条件：可以将序列划分成若干个**连续的块**，使得每个块的**第一个元素的值**恰好等于该块的长度（即该块包含的元素个数）。
求最少需要删除多少个元素才能达到要求。
你可以执行任意次操作。每次操作中，你**删除**序列中的一个元素。删除元素后，剩下的元素保持原来的相对顺序。
操作结束后，剩下的序列应满足以下条件：可以将序列划分成若干个**连续的块**，使得每个块的**第一个元素的值**恰好等于该块的长度（即该块包含的元素个数）。
求最少需要删除多少个元素才能达到要求。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数——最少需要删除的元素个数。
输入输出样例
输入 #1
7 7 3 3 4 5 2 6 1 4 5 6 3 2 6 3 4 1 6 7 7 3 1 4 3 5 1 2 3 4 5 5 1 2 3 1 2 5 4 5 5 1 5
输出 #1
0 4 1 1 2 1 0
说明/提示
### 提示
- 样例 1：删除第一个 $1$，剩下 $[1, 1]$ 是一个长度为 $2$ 的块，块首 $1 \neq 2$，但可以继续删……实际上最优是删 $1$ 个元素。
- 样例 2：$[2, 1, 3, 1]$ 本身就是合法的——$[2, 1]$ 是长度 $2$ 的块（首元素 $2$），$[3, 1]$ 是长度 $2$ 的块（首元素 $3$，但注意这里块首是 $3$ 而块长是 $2$——不对）。实际上需要按规则仔细验证。
- 核心思路：$\mathit{dp}[i]$ 表示前 $i$ 个元素中最多能保留多少个（或最少删多少个），转移时要么删掉 $a_i$，要么以 $a_i$ 开头形成一块。
- 样例 1：删除第一个 $1$，剩下 $[1, 1]$ 是一个长度为 $2$ 的块，块首 $1 \neq 2$，但可以继续删……实际上最优是删 $1$ 个元素。
- 样例 2：$[2, 1, 3, 1]$ 本身就是合法的——$[2, 1]$ 是长度 $2$ 的块（首元素 $2$），$[3, 1]$ 是长度 $2$ 的块（首元素 $3$，但注意这里块首是 $3$ 而块长是 $2$——不对）。实际上需要按规则仔细验证。
- 核心思路：$\mathit{dp}[i]$ 表示前 $i$ 个元素中最多能保留多少个（或最少删多少个），转移时要么删掉 $a_i$，要么以 $a_i$ 开头形成一块。