先把序列反转,那么问题转化为,把序列划分成尽可能多的连续段,且每一段长度比下一段短(怎么这么像CSPD2T2啊)

所以附送CSPD2T2题解链接,会对做这题有帮助

考虑暴力dp.
f[i][j]表示最后一段是(j,i]的最大高度)
易得$$f[i][j]=\max_{k<j,S(k+1,j)\le S(j+1,i)} f[k][j]+1$$
时间复杂度$O(n^3)$

类似与CSPD2T2,有引理:
定义$k$合法为$S(k+1,j)\le S(j+1,i)$
则如果存在$k1,k2$均合法,且$k1<k2$则$k2$一定不劣于$k1$.故可推得最大的合法$k$就是最优解(之一).

利用引理,我们只保存最优解,f[i]表示考虑到i的最大高度,last[i]表示最后一段的长度
转移方程:$$f[i]=\max_{k<i,last[k]\le S(k+1,i)} f[k]+1$$
时间复杂度$O(n^3)$
观察到我们还没有利用”最大的合法$k$就是最优解(之一).”的结论
用单调队列维护.
$k$可能成为$i$的最优解,仅当$last[k]\le S(k+1,i)$
那么$last[k]+s[k]\le s[i]$就合法
考虑$s[i]$递增,我们维护一个$k$递增,$last[k]+s[k]$递增的单调队列维护最优值.
如果存在$k1<k2,g[k1]+s[k1]\le g[k2]+s[k2]$那么$k1$合法时$k2$一定合法,而$k2$更优,所以$k1$没有意义.

时间复杂度$O(n)$

/**********/省略快读
#define MAXN 100011
ll f[MAXN],last[MAXN],sum[MAXN],a[MAXN];
ll s(ll l,ll r)
{
    return sum[r]-sum[l-1];
}
ll q[MAXN],h=1,t=1; 
int main()
{
    ll n=read();
    for(ll i=n;i;--i)a[i]=read();
    for(ll i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
    q[t++]=0;
    ll maxv=0;
    for(ll i=1;i<=n;++i)
    {
        //last[k]>=si-sk
        //last[k]+sk>=si
        while(h<t&&last[q[h]]<=s(q[h]+1,i))umax(maxv,q[h]),++h;
        f[i]=f[maxv]+1;
        last[i]=s(maxv+1,i);
        while(h<t&&s(1,i)+last[i]<=s(1,q[t-1])+last[q[t-1]])--t;
        q[t++]=i;
    }
    printf("%lld",f[n]);
    return 0;
}