C. Pekora and Trampoline
There is a trampoline park with n trampolines in a line. The i-th of which has strength Si.
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+Si, and Si will become equal to max(Si−1,1). In other words, Si will decrease by 1, except of the case Si=1, when Si will remain equal to 1.
If there is no trampoline in position i+Si, then this pass is over. Otherwise, Pekora will continue the pass by jumping from the trampoline at position i+Si 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 Si to 1. What is the minimum number of passes she needs to reduce all Si to 1?
Input
The first line contains a single integer t (1≤t≤500) — the number of test cases.
The first line of each test case contains a single integer n (1≤n≤5000) — the number of trampolines.
The second line of each test case contains n integers S1,S2,…,Sn (1≤Si≤10^9), where Si is the strength of the i-th trampoline.
It’s guaranteed that the sum of n over all test cases doesn’t exceed 5000.
Output
For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all Si to 1.
Example
inputCopy
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
outputCopy
4
3
0
题目大意：就是有一串蹦床，每个蹦床上有能量si，你可以选从任意一张蹦床i开始，然后你就可以跳到i+si这个位置，而且此时i位置能量-1，把从开始跳跃到跳出蹦床位置n作为一次跳跃过程，问让所有蹦床能量全部变为1的最少跳跃次数。
作为最前面且能量大于1的蹦床，如果不花费能量是不可能把他的能量降到1的，所以我们可以枚举每一个可以作为当前开始跳跃的位置。我们用freejump【i】表示位置i可以免费跳跃而不消耗跳跃的次数（免费跳跃就是指前一个位置花费了跳跃次数跳到了i+si，那此时我在从i+si跳就不花费跳跃次数了）。每一个位置免费跳跃的次数只受到了前一个位置跳跃次数的影响，那逆着过来，由当前位置i去更新每一个免费跳跃位置的信息即可。
#include <iostream>
#include<cstdio>
using namespace std;
const int N=5010;
typedef long long ll;
int num[N];
int n;
int freejump[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num[i];
freejump[i]=0;
}
ll cnt=0;
for(int i=1;i<=n;i++)
{
if(freejump[i]<num[i]-1)
{
cnt+=num[i]-freejump[i]-1;
}
for(int j=i+2;j<=i+num[i]&&j<=n;j++)
{
freejump[j]++;
}
if(freejump[i]>=num[i])
{
freejump[i+1]+=freejump[i]-num[i]+1;
}
}
cout<<cnt<<endl;
}
}