1491C - Pekora and Trampoline

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010;
int s[N];
LL cnt[N];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cnt[i]=0;
        scanf("%lld",&s[i]);
    }
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]-cnt[i]>1)//要从i这个位置跳
        {
            ans+=s[i]-1-cnt[i];//把i位置上的数减成1
            cnt[i]=s[i]-1;//把i这个位置从s[i]变成了1 自然走了s[i]-1步
        }
        for(int j=i+2;j<=min( n,i+s[i]);j++)cnt[j]++;
        cnt[i+1]+=cnt[i]-(s[i]-1);//如果之前已走比s[i]-1大 把次数累积给下一个
    }
    printf("%lld\n",ans);
}
int main()
{
    int tests=1;
    scanf("%d",&tests);
  // cin>>tests;
    //while(~scanf("%d",&n))
    while(tests--)
    {
        solve();
    }
     return 0;
}

View Code