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