题解 | Tower of Hay-牛客假日团队赛10B题

题目描述

Cows so hate the dark. In order to change a lightbulb at the top of the barn, Bessie must build a tower out of bales of hay to climb so that she can reach it. The bales of hay (conveniently numbered 1..N) enter the barn sequentially on a conveyor belt. Bale i has integer width ; all bales have depth and height of one unit.
Bessie must use all N hay bales to build the tower and must lay them down in the order they arrive. She can lay as many bales as she wishes (tightly packed in a line, of course) to create the foundation of the tower. She can then lay some of the next bales on top of the previous level to create the next level (no level can be wider than the level beneath it). She continues this process until all the bales are used. She must stack the bales in the order they arrive, from the bottom to the top of the tower. To be clear: she must not try to sneak a bale back on the foundation after a bale is placed on the second layer.
Bessie's goal is to create the tallest tower possible -- and she already knows how wide each every bale of hay will be as it comes into the barn on the belt. How tall a tower can she construct?

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer:

输出描述:

* Line 1: A single integer, the height of the tallest possible tower that can be built

示例1

输入

3
1
2
3

输出

2

说明

Use the first bales with width 1 and 2 for the bottom row (total width: 3), then the next bale (width 3) for the top row.

解答

这题首先应该会想到贪心，但马上否定掉。但此时如果你完全放弃了贪心，那么你就很可能想不到正解了。

由于此题阶段明显，可以断定用动规。在不考虑数据范围的前提下应该是很好做的。但，只能寻求更好的算法。

再回想到贪心，这时会想到一个奇葩的感觉貌似是对的，又不知如何证明的推论：

将塔看作一个面积一定图形，要使其最高，必须最瘦。

事实上这个是正确的。证明引自张昆玮大牛

任意取出一个能使层数最高的方案，设有CA层，把其中从下往上每一层最大的块编号记为；任取一个能使底边最短的方案，设有CB层，把其中从下往上每一层最大的块编号记为。显然，这说明至少存在一个k属于，满足且。也就是说，方案 A 第K 层完全被方案 B 第K 层包含。构造一个新方案，第K 层往上按方案 A，往下按方案 B，两边都不要的块放中间当第K 层。新方案的层数与 A 相同，而底边长度与 B 相同。证毕。

于是底边最短的方案，层数最高。枚举最底层由哪几块组成，由此可以得出一个方程:从到中最底层的宽度 满足 （因为这样会使得上一层的宽度不大于下一层的宽度） 且

其中

分析一下，发现（令表示宽度的前缀和），而是随i的增大而增大的，所以从到一旦发现一个符合条件的决策，便将其取出来更新。但是这仍不能通过所有数据。

再次分析，发现所有的决策的值（例如对于决策j值即为由往前都是单调递减的，也就是一个比一个优。因此决定性的因素则是他们的生效时间。

对于决策：观察不等式即,变形可得，发现便是其生效时间，也就是说在第一个使得之后到决策都是有效的。于是我们可以开一个单调队列，使得生效时间递减，并且队头始终生效并且队头未生效。由于后入队的决策比前面的优，于是一旦队头生效，队头便可弹掉。入队的时候，如果发现队尾的生效时间<队尾的生效时间，则弹掉队尾。

如此一来便完美的解决了此题，复杂度为

#include <cstdio>
const int N=100000+9;
int q[N],g[N],f[N],sum[N],w[N],n;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) {
        scanf("%d",w+i);
        sum[i]=sum[i-1]+w[i];
    }
    q[1]=n+1;
    int h=1,t=1;
    for (int i=n;i;--i) {
        while (h<t && f[q[h+1]]<=sum[q[h+1]-1]-sum[i-1]) ++h;
        f[i]=sum[q[h]-1]-sum[i-1];
        g[i]=g[q[h]]+1; 
        q[++t]=i;
        while ((t>h) && (f[q[t-1]]-sum[q[t-1]-1]+sum[q[t]-1]>f[q[t]]))
            --t,q[t]=q[t+1];
    }
    printf("%d\n",g[1]);
}