CF1453F Even Harder

Gildong 现在正在开发一款益智游戏。该游戏包含 $n$ 个编号为 $1$ 到 $n$ 的平台。玩家在游戏中扮演一个角色，可以站在每个平台上，目标是将角色从第 $1$ 个平台移动到第 $n$ 个平台。 第 $i$ 个平台上标有一个整数 $a_i$（$0 \le a_i \le n-i$）。当角色站在第 $i$ 个平台时，玩家可以将角色移动到任意 $j$ 号平台，其中 $i+1 \le j \le i+a_i$。如果角色站在 $a_i=0$ 且 $i \ne n$ 的平台上，玩家就会输掉游戏。 由于 Gildong 认为当前的游戏难度还不够，他想让游戏变得更难。他希望将一些（可能为零个）平台的标签改为 $0$，使得仅剩下唯一一条获胜路径。他希望对游戏的修改尽可能少，因此请你帮他计算，最少需要将多少个平台的标签改为 $0$，才能使仅剩下唯一一条获胜方式。两种方式不同，当且仅当存在某个平台在其中一种方式中到达，而在另一种方式中没有到达。

每组测试数据包含一个或多个测试用例。第一行为测试用例个数 $t$（$1 \le t \le 500$）。 每个测试用例包含两行。第一行为一个整数 $n$（$2 \le n \le 3000$），表示游戏的平台数量。 第二行为 $n$ 个整数，第 $i$ 个整数为 $a_i$（$0 \le a_i \le n-i$），表示第 $i$ 个平台上的整数。 保证： - 对于每个测试用例，初始时至少存在一条获胜路径。 - 所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，输出一个整数，表示最少需要将多少个平台的标签改为 $0$，才能使仅剩下一条获胜方式。

在第一个样例中，玩家只能依次移动到下一个平台，直到到达第 $4$ 个平台。由于已经只有一条获胜路径，答案为 $0$。 在第二个样例中，Gildong 可以将 $a_2$、$a_3$ 和 $a_4$ 改为 $0$，使得游戏变为 $4\ 0\ 0\ 0\ 0$。此时玩家唯一的获胜方式是直接从第 $1$ 个平台跳到第 $5$ 个平台。 在第三个样例中，Gildong 可以将 $a_2$ 和 $a_8$ 改为 $0$，此时唯一的获胜路径为：$1$ – $3$ – $7$ – $9$。 由 ChatGPT 4.1 翻译