← 返回题目列表

Codeforces · 1927/G

G. 油漆费

中文机器翻译题面 查看原题

给出了 $$$n$$$ 个单元格的水平网格带。在第 $$$i$$$ 个单元中,有大小为 $$$a_i$$$ 的油漆费用。该费用可以是:

- 要么用于左侧 - 那么左侧距离小于 $$$a_i$$$ 的所有单元格(从 $$$\max(i - a_i + 1, 1)$$$ 到 $$$i$$$ 包括在内)将被绘制,
- 或用于右侧 - 那么右侧距离小于 $$$a_i$$$ 的所有单元格(从 $$$i$$$ 到 $$$\min(i + a_i - 1, n)$$$ 包括)将被绘制,
- 或根本不使用。

请注意,一次充能只能使用一次(即不能同时向左和向右使用)。允许一个单元被多次绘制。

一次充电需要使用最少多少次来绘制条带的所有单元?

输入

输入的第一行包含一个整数 $$$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

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

输出 #1

1
2
1
1
1
3
1
2
3
4
2
3
3

注意

在示例的第三个测试用例中,使用右侧 $$$1$$$-st 单元格的电荷就足够了,然后它将覆盖 $$$1$$$ 和 $$$2$$$ 两个单元格。

在示例的第九个测试用例中,您需要:

- 使用左侧 $$$3$$$-rd 单元格的电荷,覆盖从 $$$1$$$-st 到 $$$3$$$-rd 的单元格;
- 使用左侧第 $$$5$$$ 个单元格的电荷,覆盖从第 $$$4$$$ 到第 $$$5$$$ 的单元格;
- 使用左侧第 $$$7$$$ 个单元格的电荷,覆盖从第 $$$6$$$ 到第 $$$7$$$ 的单元格。

在示例的第十一个测试用例中,您需要:

- 使用右侧第$$$5$$$个单元格的电荷,覆盖从第$$$5$$$个单元格到第$$$10$$$个单元格;
- 使用左侧第 $$$7$$$ 单元格的电荷,覆盖从 $$$1$$$ 单元格到第 $$$7$$$ 单元格。