某岛

… : "…アッカリ~ン . .. . " .. .
December 21, 2012

BZOJ 1233. [Usaco2009Open]干草堆tower

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