很巧妙的一道题。不再是决策点以dp值中一部分含j项为维护对象，而是通过维护条件来获取决策。
首先有个贪心策略，让底层的宽度尽可能小，才能让高度尽可能高。所以应该倒着dp，表示堆$i~n$的最高高度$f[i]$，同时这种最值应来源于之后的j,要在设一个$g[i]$表示以i为底层,最窄的宽度。这个的话真的只可意会啊。
所以dp方程就能出来了
$g[i]=min(sum[j-1]-sum[i-1]) g[j]<=sum[j-1]-sum[i-1]$
$f[i]=f[j]+1$
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 typedef long long ll; 8 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 9 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 10 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 11 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 12 template<typename T>inline T read(T&x){ 13 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c==‘-‘)f=1; 14 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 15 } 16 const int N=100000+7; 17 int sum[N],f[N],g[N],q[N]; 18 int n,l,r; 19 20 int main(){//freopen("test.in","r",stdin);//freopen("tmp.out","w",stdout); 21 read(n);for(register int i=1;i<=n;++i)sum[i]=read(sum[i])+sum[i-1]; 22 l=1,r=1;q[l]=n+1; 23 for(register int i=n;i;--i){ 24 while(l<r&&sum[q[l+1]-1]-g[q[l+1]]>=sum[i-1])++l; 25 g[i]=sum[q[l]-1]-sum[i-1],f[i]=f[q[l]]+1; 26 while(l<=r&&sum[q[r]-1]-g[q[r]]<=sum[i-1]-g[i])--r; 27 q[++r]=i; 28 } 29 printf("%d\n",f[1]); 30 return 0; 31 }
BZOJ1233 [Usaco2009Open]干草堆tower[贪心+单调队列优化]
原文：https://www.cnblogs.com/saigyouji-yuyuko/p/10453611.html