lzh的蹦床

sky被lzh抓到了一间密室，密室里放了一排紧密相邻的蹦床，lzh声称自己最喜欢欣赏sky跳跃在空中的姿态，并示意他可以开始跳了。sky的跳跃方向是单向向前的，当然如果他落到一个蹦床上则会继续向前弹跳，
直到sky落到了坚硬可靠的地面上，他才可以结束这一趟弹跳，lzh当然允许sky自己选择每一趟跳跃开始的蹦床。
每一个蹦床都有它的弹力值 $b_i$ ，这决定了从该蹦床起跳后的落点--通俗来说，从 $i\$ 蹦床起跳将会落到 ${i+b_i}$ 蹦床上（假如这个位置有蹦床）。但由于sky心中有怨气，他便不会爱惜的使用lzh珍藏已久的蹦床，所以，
可惜的是，他每一次的起跳都会造成当前蹦床的弹力值 $-1$ ，但幸好lzh的蹦床是为了sky的安全设计的，也就是说，这个蹦床的弹力值不会低于 $1$ 。sky饿的不行了，他想尽早回宿舍，他观察到lzh对他进行距离为 $1$ 的跳跃（
也就是从 $a_i$ 跳到 $a_i+1$ ）不怎么感兴趣，他打算使所有蹦床弹力值都变成 $1$ ，这样他就可以回宿舍吃饭了，请你帮帮他，计算出他最少需要跳多少趟。

第一行输入一个正整数 $T(T \leq 500)$ ，表示测试用例的个数
接下来 $T$ 个用例，
每个用例第一行一个正整数 $n(1 \leq n \leq 5000)$ ,表示蹦床的数量;
第二行有 $n$ 个正整数 $b_i$ $(1 \leq b_i \leq 10^9)$ ，表示每个蹦床的弹力值。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[5010]; int d[5010]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _; cin>>_; while(_--){ memset(d,0,sizeof(d)); int n; cin>>n; ll ans=0,cnt=0; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ cnt+=d[i]; if(a[i]-1>cnt) ans+=a[i]-cnt-1; else{ d[i+1]+=cnt-a[i]+1; d[i+2]-=cnt-a[i]+1; } if(a[i]>1){ d[min(5001,i+a[i]+1)]--; d[i+2]++; } } cout<<ans<<"\n"; } return 0; }

详情