Brief description:

… 按顺序摆放 n 捆干草堆 。。。问最高可以叠多少层。。
（每一级不能比下面一级宽。。。

Analysis:

。。有个看上去“显然”的贪心。。（不过是错误的。。
。正确做法是证一个结论（在多种可行的堆叠方案中，至少有一种能使层数最高的方案同时使得底边最短。）。。然后单调队列 DP 。。

。。还是直接贴 秋醒半梦时 的题解好了。。。。

我最开始就犯了一个严重的错误，误以为这题是贪心。怎么贪呢，就是最后一块作顶层，然后每次选到大于等于上一层就停止这一层，开始选下一层。
乍一看好像是没问题，可是其实是不对的。什么？你也觉得是对的，请看下面一组数据。

5 
11 
5 
5 
2 
8

这样贪心的结果是2，其实答案应该是3。
问题就来了，我们这样贪心的思路是尽量给下面的多留干草包，可这样不一定是最优解。那么我们反过来，尽量给上面多留干草包呢？
抽象化一点，便是：在多种可行的堆叠方案中，至少有一种能使层数最高的方案同时使得底边最短。即底边最短的，层数一定最高。
事实证明，这样是正确的。证明？引用一段张昆玮大牛的：

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

现在的问题是，怎么给上面多留干草包，又保证有解呢？

设F[i]为第i..N个干草包所叠成的塔底层最短边的值。
tot[i]为1..i的干草堆宽度和。

显然F[i]=min(tot[j-1]-tot[i-1]) j>i 且 tot[j-1]-tot[i-1]>=F[j]
不难看出这样的解法是O(n^2)，可过9个点(一共15个点)。

可以用单调队列来优化。
现在有j=F[x]。
那么如果f[k]-(tot[k-1]-tot[j-1])却不能<=f[j]的话，k就没有了一点优势，即不可能存在用k不用j的情况。 .. .

干草堆tower.cpp"]
/* .................................................................................................................................. */

const int N = 100009;
int f[N], g[N], s[N], q[N], cz, op;
// f[i] = s[j] - s[i], 从 i+1 位置开始堆最高时底层的最小宽度。
// g[i] 从 i+1 位置开始时最高可以堆多少层。
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    REP_C(i, RD(n)) s[i+1] = s[i] + RD();

    g[n] = 0, q[cz = 0] = n, op = 0; DWN(i, n, 0){
        while (cz < op && f[q[cz+1]] <= s[q[cz+1]] - s[i]) ++cz;
        f[i] = s[q[cz]] - s[i], g[i] = g[q[cz]] + 1;
        while (cz <= op && f[q[op]] - s[q[op]] >= f[i] - s[i]) --op;
        q[++op] = i;
    }

    OT(g[0]);
}

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=1233
http://zzlqxbms.diandian.com/post/2010-06-09/16044788

Posted by xiaodao
Category: BZOJ
Tags: 单调队列