Pekora and Trampoline

题意翻译

有 $n$ 个蹦床排成一列，每个蹦床有一个弹力值 $s_i$ 每一轮的最开始，Pekora 会选择一个蹦床作为她的起点（任意一个蹦床都可以作为起点）。当她在蹦床 $i$ 时，她会跳到蹦床 $i+s_i$ 上，并且 $s_i$ 会变为 $\max(1,s_i-1)$（也就是说，蹦床每被跳一次弹力值就会减一，直到弹力值为 $1$）。当她跳到了第 $n$ 个蹦床的后面时，该轮结束。 现在，Pekora 想要把所有的 $s_i$ 都变成 $1$，问最少要多少轮才能实现这个目标 ### 输入格式 **本题有多组数据** 第一行一个整数 $T$，表示数据的组数 对于每组数据： 第一行一个整数 $n$，表示蹦床的个数 第二行 $n$ 个整数，分别为 $s_{1\dots n}$ ### 输出格式 共$T$ 行，每行一个整数表示该组数据的答案 **说明与提示** $1 \le T \le 500$ $\sum n \le 5000$ $1 \le s_i \le 10^9$

题目描述

There is a trampoline park with $ n $ trampolines in a line. The $ i $ -th of which has strength $ S_i $ . Pekora can jump on trampolines in multiple passes. She starts the pass by jumping on any trampoline of her choice. If at the moment Pekora jumps on trampoline $ i $ , the trampoline will launch her to position $ i + S_i $ , and $ S_i $ will become equal to $ \max(S_i-1,1) $ . In other words, $ S_i $ will decrease by $ 1 $ , except of the case $ S_i=1 $ , when $ S_i $ will remain equal to $ 1 $ . If there is no trampoline in position $ i + S_i $ , then this pass is over. Otherwise, Pekora will continue the pass by jumping from the trampoline at position $ i + S_i $ by the same rule as above. Pekora can't stop jumping during the pass until she lands at the position larger than $ n $ (in which there is no trampoline). Poor Pekora! Pekora is a naughty rabbit and wants to ruin the trampoline park by reducing all $ S_i $ to $ 1 $ . What is the minimum number of passes she needs to reduce all $ S_i $ to $ 1 $ ?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 5000 $ ) — the number of trampolines. The second line of each test case contains $ n $ integers $ S_1, S_2, \dots, S_n $ ( $ 1 \le S_i \le 10^9 $ ), where $ S_i $ is the strength of the $ i $ -th trampoline. It's guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 5000 $ .

输出格式

For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $ S_i $ to $ 1 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

4
3
0

说明

For the first test case, here is an optimal series of passes Pekora can take. (The bolded numbers are the positions that Pekora jumps into during these passes.) - $ [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}] $ For the second test case, the optimal series of passes is show below. - $ [\textbf{2},3] $ - $ [1,\textbf{3}] $ - $ [1,\textbf{2}] $ For the third test case, all $ S_i $ are already equal to $ 1 $ .

题意翻译

有 $n$ 个蹦床排成一列，每个蹦床有一个弹力值 $s_i$ 每一轮的最开始，Pekora 会选择一个蹦床作为她的起点（任意一个蹦床都可以作为起点）。当她在蹦床 $i$ 时，她会跳到蹦床 $i+s_i$ 上，并且 $s_i$ 会变为 $\max(1,s_i-1)$（也就是说，蹦床每被跳一次弹力值就会减一，直到弹力值为 $1$）。当她跳到了第 $n$ 个蹦床的后面时，该轮结束。 现在，Pekora 想要把所有的 $s_i$ 都变成 $1$，问最少要多少轮才能实现这个目标 ### 输入格式 **本题有多组数据** 第一行一个整数 $T$，表示数据的组数 对于每组数据： 第一行一个整数 $n$，表示蹦床的个数 第二行 $n$ 个整数，分别为 $s_{1\dots n}$ ### 输出格式 共$T$ 行，每行一个整数表示该组数据的答案 **说明与提示** $1 \le T \le 500$ $\sum n \le 5000$ $1 \le s_i \le 10^9$