311056: CF1927G. Paint Charges
Description
A horizontal grid strip of $n$ cells is given. In the $i$-th cell, there is a paint charge of size $a_i$. This charge can be:
- either used to the left — then all cells to the left at a distance less than $a_i$ (from $\max(i - a_i + 1, 1)$ to $i$ inclusive) will be painted,
- or used to the right — then all cells to the right at a distance less than $a_i$ (from $i$ to $\min(i + a_i - 1, n)$ inclusive) will be painted,
- or not used at all.
Note that a charge can be used no more than once (that is, it cannot be used simultaneously to the left and to the right). It is allowed for a cell to be painted more than once.
What is the minimum number of times a charge needs to be used to paint all the cells of the strip?
InputThe first line of the input contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the test. This is followed by descriptions of $t$ test cases.
Each test case is specified by two lines. The first one contains an integer $n$ ($1 \le n \le 100$) — the number of cells in the strip. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the size of the paint charge in the $i$-th cell from the left of the strip.
It is guaranteed that the sum of the values of $n$ in the test does not exceed $1000$.
OutputFor each test case, output the minimum number of times the charges need to be used to paint all the cells of the strip.
ExampleInput13 1 1 2 1 1 2 2 1 2 1 2 2 2 2 3 1 1 1 3 3 1 2 3 1 3 1 7 1 2 3 1 2 4 2 7 2 1 1 1 2 3 1 10 2 2 5 1 6 1 8 2 8 2 6 2 1 2 1 1 2 6 1 1 4 1 3 2Output
1 2 1 1 1 3 1 2 3 4 2 3 3Note
In the third test case of the example, it is sufficient to use the charge from the $1$-st cell to the right, then it will cover both cells $1$ and $2$.
In the ninth test case of the example, you need to:
- use the charge from the $3$-rd cell to the left, covering cells from the $1$-st to the $3$-rd;
- use the charge from the $5$-th cell to the left, covering cells from the $4$-th to the $5$-th;
- use the charge from the $7$-th cell to the left, covering cells from the $6$-th to the $7$-th.
In the eleventh test case of the example, you need to:
- use the charge from the $5$-th cell to the right, covering cells from the $5$-th to the $10$-th;
- use the charge from the $7$-th cell to the left, covering cells from the $1$-st to the $7$-th.
Output
给定一个水平排列的n个单元格的网格条。在第i个单元格中，有一个大小为a_i的颜料电荷。这个电荷可以有以下三种使用方式：
1. 向左使用：那么距离小于a_i的所有左侧单元格（从max(i - a_i + 1, 1)到i，包括i）将被涂色。
2. 向右使用：那么距离小于a_i的所有右侧单元格（从i到min(i + a_i - 1, n)，包括i）将被涂色。
3. 不使用。
注意，一个电荷最多只能使用一次（即，不能同时向左和向右使用）。一个单元格被多次涂色是允许的。
问：需要使用电荷的最少次数才能涂满整个网格条的所有单元格？
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 100），表示测试用例的数量。接下来是t个测试用例的描述。
- 每个测试用例由两行组成。第一行包含一个整数n（1 ≤ n ≤ 100），表示网格条中的单元格数量。第二行包含n个正整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n），其中a_i是从网格条左侧数起第i个单元格中的颜料电荷大小。
- 保证测试中n的值的总和不超过1000。
输出：
- 对于每个测试用例，输出使用电荷的最少次数，以涂满网格条的所有单元格。
示例输入输出（提供了一些测试用例的输入输出对，用于说明问题）。
注意：题目中的公式使用LaTeX格式。题目大意： 给定一个水平排列的n个单元格的网格条。在第i个单元格中，有一个大小为a_i的颜料电荷。这个电荷可以有以下三种使用方式： 1. 向左使用：那么距离小于a_i的所有左侧单元格（从max(i - a_i + 1, 1)到i，包括i）将被涂色。 2. 向右使用：那么距离小于a_i的所有右侧单元格（从i到min(i + a_i - 1, n)，包括i）将被涂色。 3. 不使用。 注意，一个电荷最多只能使用一次（即，不能同时向左和向右使用）。一个单元格被多次涂色是允许的。 问：需要使用电荷的最少次数才能涂满整个网格条的所有单元格？ 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 100），表示测试用例的数量。接下来是t个测试用例的描述。 - 每个测试用例由两行组成。第一行包含一个整数n（1 ≤ n ≤ 100），表示网格条中的单元格数量。第二行包含n个正整数a_1, a_2, …, a_n（1 ≤ a_i ≤ n），其中a_i是从网格条左侧数起第i个单元格中的颜料电荷大小。 - 保证测试中n的值的总和不超过1000。 输出： - 对于每个测试用例，输出使用电荷的最少次数，以涂满网格条的所有单元格。 示例输入输出（提供了一些测试用例的输入输出对，用于说明问题）。 注意：题目中的公式使用LaTeX格式。