C.PekoraandTrampoline(CodeforcesGlobalRound13)题解xiaodangao

题目链接：C. Pekora and Trampoline
思路：差分，经过仔细思考可以发现，最优解一定是都在1这个位置进行跳跃，因为假设1这个位置上的a[1]=1，那么他会跳到2，也就是具有传递性，直到跳到一个value不为1的地方，这和一开始就在该位置跳是一样的。证明了这个之后，我们进一步思考可以发现，i这个位置，可以对后面[i+2,min(a[i]+i,n)]产生影响，产生的影响是后面这些用跳的次数-1，然后再根据a[i]=1的传递性，如果位置j的value已经降为了1，那么前面对他的贡献可以继续延伸到j+1，对于每一个数对于后面产生的影响，我们可以用一个差分数组 $\Theta(1)$ 的完成
$Code:$


#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 5e3+10;
int _,n;
int a[N],sum[N];
void work(int now,int l){
    if(now<l)return ;
    int y = min(now,n);
    int x = min(l,n);
    if(l > n)x = n+1;
    sum[x]++;
    sum[y+1]--;
}
void solve(){
    read(_);
    while(_--){
        memset(sum,0,sizeof sum);
        read(n);
        rep(i,1,n){
            read(a[i]);
        }
        rep(i,1,n){
            work(a[i]+i,i+2);
        }
        int now = 0;
        ll ans = 0;
        rep(i,1,n){
            now+=sum[i];
            //int p = now;
            if(a[i] - now< 1){
                sum[i+1] += now - a[i] + 1;
                sum[i+2] -= now - a[i] + 1;
                a[i] = 0;
            }
            a[i]-=now;
            a[i]--;
            a[i] = max(a[i],0);
            ans+=(ll)a[i];
            //write(max(a[i],0));pc(' ');
        }
        write(ans);pc('\n');
    }
}
signed main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。