Acw331.干草堆

题意：

给定n个草堆堆在一起，问最高能堆多高。

要求底边一定要宽于对应顶边。

思路：

首先可以贪心的想，在所有可行方案中，一定有一种层数最高的方案是底边最短的。

也就是说底边最短的可行方案，就是层数最高的方案。

• 此结论由zkw严格证明。

从这个方向入手，我们可以先把$a$数组反过来后并求前缀和$s(i)$。

$f(i)$表示考虑到位置$i$时，$a_1$~$a_i$能搭多少层，$g(i)$表示$i$作为最后一层的最小宽度。

有转移方程：
$$ f(i)=f(j)+1 $$
其中$j$为满足$j\in[0,i-1]$且$g(j)\leq s(i)-s(j)$的最后一个$j$。

对于$g(i)$，$g(i)=s(i)-s(j)$。

枚举$i$后枚举$j$，此时复杂度为$O(n^2)$，无法通过。

考虑优化。

转移条件为：
$$ g(j)\leq s(i)-s(j)\\\\ g(j)+s(j)\leq s(i) $$
那么就会有：

设$k<j$，如果$g(k)+s(k) \geq g(j)+s(j)$，那么显然$j$是一个更好的答案，放弃$k$。

所以我们维护一个$(g+s)$的单调递增的单调队列即可。

时间复杂度：$O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n, a[maxn], s[maxn];
int f[maxn];
int g[maxn];
int q[maxn];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    reverse(a+1, a+1+n);
    for(int i = 1; i <= n; i++) s[i] = s[i-1]+a[i];
    int hh = 1, tt = 0;
    for(int i = 1; i <= n; i++)
    {
        while(hh <= tt && s[q[hh]]+g[q[hh]] <= s[i]) hh++;
        //此时的队头不符合条件 但是hh-1符合条件
        f[i] = f[q[hh-1]]+1; g[i] = s[i]-s[q[hh-1]];
        while(hh <= tt && s[q[tt]]+g[q[tt]] >= s[i]+g[i]) tt--;
        q[++tt] = i;
    }
    cout << f[n] << endl;
}