Tower of Hay

https://ac.nowcoder.com/acm/problem/24881

题号 NC24881
名称 Tower of Hay
来源 USACO

题目描述

按顺序给你n个草堆，每个草垛高度为1，宽度为w，每次你可以将草垛合并（合并后高度不变，宽度为两个草垛宽度之和），也可以将草垛累高（一个草垛x，放在另一个草垛y的条件是，y是最高的那个草垛并且，y的宽度要大于等于x的宽度），操作的顺序必须按照草垛给定的顺序，问将所有草垛用完后能累成的最大高度的草堆是多少？

样例

输入
3
1
2
3
输出
2

最优的操作方式是
3
12
__________
1
2
3
是不合法的因为没有按照草垛给定的顺序操作

算法

(dp + 单调队列优化 + 贪心)

比较直接的一个想法是让草堆最底部的宽度尽可能的大

但这样就未必能得到最大的高度

另一个想法是让草堆最底部的宽度尽可能的小，最后草堆的高度就可能越高

而这个思路明显是错误的，当遇到一个宽度比当前最高的那个草垛的宽度还宽的草堆时，前面的所有草垛都要推翻重新摆过了

为了能让贪心顺利的进行下去，我们考虑从后往前进行操作

假设[j + 1,n]个草垛我们合法摆好之后，接下来的[1,j]个草垛就需要组成一个新的底部或者合并到已经摆好的草堆最底部

只要sum[1] - sum[j + 1]的大小比最低层的草垛宽就能新加一层，否则也能直接合并到最后一层

我们只需要保证[j + 1,n]个草垛组成的草堆最底部的宽度最小，那么组成新底部的草垛个数就可能越少，最后高度就可能越高

好那么我们现在维护f[i]表示用合法的方式将[i,n]个草垛搭成草堆的最大高度，g[i]表示高度为f[i]的草堆最底层的最小宽度是多少

状态计算：(从后往前枚举i)

$f[i] = max(f[j]) + 1 (j \in [i + 1,n],sum[i] - sum[j] >= g[j])$

$g[i] = min(sum[i] - sum[j]) (f[j] + 1 = f[i])$

我们发现这样计算时间复杂度是 $O(n^2)$ 的

$sum[i] - sum[j] >= g[j]$ 等价于 $sum[i] >= g[j] + sum[j]$

我们发现g[j] 和 sum[j]随着j减少而增大，因为sum[j]是后缀和并且w都是正数所以递增

而g[j]因为底层的宽度一定是大于等于高层的所以非降

所以g[j] + sum[j]整体是递增的，

而由于f[i]的更新方式是 $f[i] = max(f[j]) + 1 (j \in [i + 1,n])$ ，所以f[i]也是随着j减少而增加的

我们可以用一个单调递增队列维护下标

（声明一点队首下标大，队尾下标小）

每次从队头找到最后一个 $sum[i] >= g[队首] + sum[队首]$ 的下标，其余的都出队（下标越小f就可能越大，所以只需要最后一个）

接着将队尾所有sum[队尾] + g[队尾] >= sum[i] + g[i],从队列中删去

（队列中的元素下标都比i大所以f都比f[i]小，而sum + g的值又比sum[i] + g[i]大，那么一定没有i优）

整个过程每个元素入队一次出队一次，所以总的时间复杂度是 $O(n)$ 的

细节：

我们用一个变量pos存储最后一个满足 $sum[i] >= g[队首] + sum[队首]$ 的下标

有两个好处：

开始时队列为空将pos置为n + 1，可以让f[n] = 1,g[n] = sum[n]
我们在查找最后一个 $sum[i] >= g[队首] + sum[队首]$ 的下标的最后会将包括答案在内的下标都出队（详见代码）。而pos不仅可以更新

f[i]，还可能可以更新f[i - 1]。不用pos记录会导致有些情况f[i - 1]无法被更新

时间复杂度 $O(n)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
LL sum[N];
int a[N],q[N];
int f[N],g[N];
int n;

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = n;i >= 1;i --) sum[i] = sum[i + 1] + a[i];
    int hh = 0,tt = 0;
    int pos = n + 1;
    for(int i = n;i >= 1;i --)
    {
        while(hh <= tt && sum[i] >= g[q[hh]] + sum[q[hh]])
        {
            pos = q[hh];
            hh ++;
        }
        f[i] = f[pos] + 1;
        g[i] = sum[i] - sum[pos];
        while(hh <= tt && sum[q[tt]] + g[q[tt]] >= sum[i] + g[i]) tt --;
        q[++ tt] = i;
    }
    printf("%d\n",f[1]);
}

int main()
{
    /*#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL*/
    int T = 1;
    // init(N - 1);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

PS：以前只知道单调队列维护一个滑动窗口来优化dp。这道题是一种没见过的使用方式