Paint Charges
Contest: Codeforces Round 923 (Div. 3)
Difficulty rating: 2300
Tags: data structures, dp, greedy, math

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?

Input format:
The 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$$$.

Output format:
For each test case, output the minimum number of times the charges need to be used to paint all the cells of the strip.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
13
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 2

Example output:
1
2
1
1
1
3
1
2
3
4
2
3
3

Editorial:
Let's use the method of dynamic programming. Let $$$dp[i][j][k]$$$ be the minimum number of operations required for the distance from $$$i$$$ to the farthest unpainted cell on the left to be $$$j$$$, and to the nearest unpainted cell on the right to be $$$k$$$ (including itself).
We will update the values forward, that is, for all reachable states, we will find the states reachable from it and update the answer for them. In this case, we will move from the current $$$i$$$ to $$$i + 1$$$, recalculating $$$j$$$ and $$$k$$$ depending on the action: not spraying paint from $$$i$$$, spraying paint from $$$i$$$ to the left, spraying paint from $$$i$$$ to the right.
The problem could also have been solved in $$$O(n^2)$$$, however, the constraints did not require this.