CF1927G Paint Charges

给定一个长度为 $n$ 的水平网格带。第 $i$ 个格子中有一个大小为 $a_i$ 的涂料装置。每个装置可以： - 向左使用 —— 那么距离 $a_i$ 以内的所有左侧格子（从 $\max(i - a_i + 1, 1)$ 到 $i$，包括 $i$）都会被涂色； - 向右使用 —— 那么距离 $a_i$ 以内的所有右侧格子（从 $i$ 到 $\min(i + a_i - 1, n)$，包括 $i$）都会被涂色； - 或者不使用。 注意，每个装置最多只能使用一次（即不能同时向左和向右使用）。同一个格子可以被多次涂色。 问：最少需要使用多少次装置，才能将整个网格带的所有格子都涂色？

输入的第一行为一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。 每个测试用例包含两行。第一行为一个整数 $n$（$1 \le n \le 100$），表示网格带的格子数量。第二行为 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），其中 $a_i$ 表示第 $i$ 个格子的涂料装置的大小。 保证所有测试用例中 $n$ 的总和不超过 $1000$。

对于每个测试用例，输出一个整数，表示最少需要使用多少次装置才能将所有格子涂色。

在样例的第三个测试用例中，只需将第 $1$ 个格子的装置向右使用，就可以覆盖第 $1$ 和第 $2$ 个格子。 在样例的第九个测试用例中，需要： - 将第 $3$ 个格子的装置向左使用，覆盖第 $1$ 到第 $3$ 个格子； - 将第 $5$ 个格子的装置向左使用，覆盖第 $4$ 到第 $5$ 个格子； - 将第 $7$ 个格子的装置向左使用，覆盖第 $6$ 到第 $7$ 个格子。 在样例的第十一个测试用例中，需要： - 将第 $5$ 个格子的装置向右使用，覆盖第 $5$ 到第 $10$ 个格子； - 将第 $7$ 个格子的装置向左使用，覆盖第 $1$ 到第 $7$ 个格子。 由 ChatGPT 4.1 翻译