AC331. 干草堆

首先感谢whsstory的题解，读者可以先看一下大佬的题解

1. 为什么要倒序处理？

因为倒序处理能够使答案具有单调性

​ 设 $d[i]$ 为 前 i 堆能够到达的高度， $last[i]$ 表示第 $i$ 堆的宽度。显然$d[i]$ 随 $i$ 递增而递增，对于$d[i]$, 我们是找到一个最大的 $j$ ，在满足$last[j] \le s[i] - s[j]$ 的条件下进行如下转移 $s[i] = s[j] + 1$ 。

​ 因为我们找到的是最大的$j$ ，这保证了在所有决策中$d[j]$ 是最大的，并且$last[i]$ 是最小的(因为$last[i] = s[i]-s[j]$), $last[i]$ 最小这件事情保证了之后的某个状态$d[k]$ 在选择 i 作为决策时，有最优的决策影响条件$last[i]$是否小于$s[k]-s[i]$ 。

​ 之后就是维护一个 $g[j] = s[j] + last[j]$ 随 $j$ 单调递增的单调队列，向$d[i]$ 转移时，要保证队头决策$j$ 是满足$s[j]+last[j]\le s[i]$ 最大的那个$j$。决策入队时满足队尾单调性即可

const int N = 100000 + 5;
int n, a[N], s[N], last[N], q[N], l, r;
int d[N];
int main()
{
    scanf("%d", &n);
    for (int i = n; i >= 1;i--)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n;i++)
        s[i] = s[i - 1] + a[i];
    l = 0, r = -1;
    q[++r] = 0;
    for (int i = 1; i <= n;i++){
        while (l <= r - 1 && s[q[l+1]] + last[q[l+1]] <= s[i])
            l++;
        d[i] = d[q[l]] + 1;
        last[i] = s[i] - s[q[l]];
        while(l <= r && s[q[r]] + last[q[r]] >= s[i] + last[i])
            r--;
        q[++r] = i;
    }
    cout << d[n] << endl;
    return 0;
}