← 返回题目列表

Codeforces · 1491/C

C. 佩科拉和蹦床

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

有一个蹦床公园,里面有 $$$n$$$ 的蹦床排成一排。其中第 $$$i$$$ 的强度为 $$$S_i$$$。

佩科拉可以多次在蹦床上跳跃。她从跳上她选择的任何蹦床上开始传球。

如果此刻 Pekora 在蹦床上跳 $$$i$$$,蹦床会将她发射到位置 $$$i + S_i$$$,并且 $$$S_i$$$ 将等于 $$$\max(S_i-1,1)$$$。换句话说,$$$S_i$$$将减少$$$1$$$,除了$$$S_i=1$$$的情况,此时$$$S_i$$$将保持等于$$$1$$$。

如果 $$$i + S_i$$$ 位置没有蹦床,则本次传递结束。否则,Pekora 将按照与上述相同的规则,从 $$$i + S_i$$$ 位置的蹦床跳下去,继续传球。

Pekora 在传球过程中无法停止跳跃,直到她降落在大于 $$$n$$$ 的位置(其中没有蹦床)。可怜的佩科拉!

Pekora 是一只顽皮的兔子,他想通过将所有 $$$S_i$$$ 减少到 $$$1$$$ 来毁掉蹦床公园。将所有 $$$S_i$$$ 减少到 $$$1$$$ 所需的最少通过次数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$) — 蹦床的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$S_1, S_2, \dots, S_n$$$ ($$$1 \le S_i \le 10^9$$$),其中 $$$S_i$$$ 是第 $$$i$$$ 个蹦床的强度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个整数 - Pekora 需要执行的最小传递次数才能将所有 $$$S_i$$$ 减少到 $$$1$$$。

示例

输入 #1

3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1

输出 #1

4
3
0

注意

对于第一个测试用例,这里是 Pekora 可以采取的一系列最佳传递。 (粗体数字是佩科拉在这些传球过程中跳入的位置。)

- $$$[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$$$
- $$$[1,\textbf{4},1,2,1,\textbf{2},1]$$$
- $$$[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$$$
- $$$[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$$$

对于第二个测试用例,最佳的通过系列如下所示。

- $$$[\textbf{2},3]$$$
- $$$[1,\textbf{3}]$$$
- $$$[1,\textbf{2}]$$$

对于第三个测试用例,所有 $$$S_i$$$ 已经等于 $$$1$$$。