又是一道单调队列优化dp的题目 这道题呢 先要了解一个结论，在多种可行的堆叠方案中，至少有一种能使层数最高的方案同时使得底边最短。即底边最短的，层数一定最高。 这个是zkw大神得出的 我也不会证明来着 反正这样之后我们就可以得出正确的方法了

递推式 F[i]=min(sum[j-1]-sum[i-1])  j>i 且 sum[j-1]-sum[i-1]>=F[j] 易得在满足的条件下j当然是越小越好了嘛 而这样得出的方程又满足一定的单调性 这样调整之后队首就是我们要的答案啦

又对于转移条件 f[j]<=sum[j−1]−sum[i−1]f[j]<=sum[j−1]−sum[i−1] 我们把式子移项得到 sum[i−1]<=sum[j−1]−f[j] 所以若k>j且sum【k-1】-f【k】>=sum【j-1】-f【j】那k一定不是最优解就可以舍弃啦

剩下的看看代码吧

#include
      
       #include
       
        #include
        
         using namespace std;const int M=100007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;} int f[M],g[M],sum[M],q[M],head,tail,n,w;int main(){    n=read();    for(int i=1;i<=n;i++) w=read(),sum[i]=sum[i-1]+w;    q[0]=n+1;    for(int i=n;i;i--){        while(head
         
          =f[q[head+1]]) head++;        f[i]=sum[q[head]-1]-sum[i-1];        g[i]=g[q[head]]+1;        while(head
          
           <=f[q[tail]]-sum[q[tail]-1]) tail--;        q[++tail]=i;    }    printf("%d\n",g[1]);    return 0;}