[NC13A]反蝴蝶效应/[SPOJ-NPC2014D]General Joke

题目大意：

按顺序访问\(A_{1\sim n}(n\le10^5)\)，经过\(A_i\)时身上必须有\(A_i\)的能量，每经过一个点消耗\(1\)能量，问一开始至少多少能量？

思路：

\(f[i]\)表示从后往前倒推到第\(i\)个点需要多少能量，则\(f[i]=\max(A_i,f[i+1]+1)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

    register char ch;

    while(!isdigit(ch=getchar()));

    register int x=ch^'0';

    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

    return x;

}

const int N=1e5+1;

int a[N];

int main() {

    const int n=getint();

    for(register int i=1;i<=n;i++) a[i]=getint();

    for(register int i=n-1;i>=1;i--) {

        a[i]=std::max(a[i],a[i+1]+1);

    }

    printf("%d\n",a[1]);

    return 0;

}