Description：

给 $n$ 个长方体，每个长方体高度相同但长度不同，按照给出的顺序摆放，要求每一层要比下一层宽，问最高能摆几层。

$1\le n \le 10^5$

Solution：

首先有一个性质，最下层最窄的方案一定也是一个最高的方案。

考虑这样一组数据：

$4$

$2\ 1\ 4$

如果只有前两个数，那么最高可以堆 $2$ 层，加入第 $3$ 个数后就只能堆一层了，所以正向转移时是没有单调性的，原因就在于后面新加的可能会强制把原来垒起来的拆下来。

但是倒序转移就没有这个问题，因为最下层已经确定，后面的层高也不会变，所以答案是单调的。

可以倒序设计一个 $n^2$ 的 $DP$ ，即同时维护到第 $i$ 包干草最下层宽度 $f[i]$ 和高度 $g[i]$ ，枚举上一层最后一个干草的位置即可 $O(n)$ 转移，然而这样的复杂度是承受不了的。

先把方程列出来： $f[i]=\min(sum[j-1]-sum[i-1] (j > i,f[j]\le sum[j - 1]-sum[i - 1]))$

$g[i]=g[j]+1$

考虑单调队列优化 $DP$ 的方式，是把所有在未来都不可能比这个决策优的最优决策的方案都删掉，那么队列中维护的是位置越来越靠后，决策越来越劣的方案。

为什么位置越来越靠后，是因为他在未来更合法。把条件移项，得 $sum[i-1]\le sum[j-1]-f[j]$ ，也就是说 $sum[k-1]-f[k]$ 越大越容易合法，而且随着 $f$ 的增大在将来可能更优，从转移来看， $sum[i-1]$ 越小越好，即 $i$ 越小越好。

所以应该维护一个 $sum[k-1]-f[k]$ 单调递增， $k$ 单调递增的队列，即如果 $k > i$ 且 $sum[k-1]-f[k]\le sum[i - 1] - f[i]$ ，那 $k$ 就没用了。

所以这其实是一个变形的单调队列优化 $DP$ ，由于决策越靠后越优，所以队头并不一定是最优解，只要接下来的满足条件，就不停弹队头。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int q[MAXN],head = 1,tail = 0;

int sum[MAXN];

int f[MAXN],g[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		sum[i] = sum[i - 1] + a[i];

	}

	q[++tail] = n + 1;

	f[n + 1] = 0;g[n + 1] = 0;

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

	{

		while(head < tail && f[q[head + 1]] <= sum[q[head + 1] - 1] - sum[i - 1])++head;

		f[i] = sum[q[head] - 1] - sum[i - 1];

		g[i] = g[q[head]] + 1;

		while(head <= tail && sum[q[tail] - 1] - f[q[tail]] <= sum[i - 1] - f[i])--tail;

		q[++tail] = i;

	}

	cout << g[1] << endl;

	return 0;

}