GCJ 2019 Round3 B

Problem B. Pancake Pyramid

Brief Description

給定長度為 n 的序列 h[i]。
每次你可以選擇一段連續子序列 [l, r],你可以給其中某些項執行 +1 操作,使得操作後形成一個金字塔形狀(先遞增再遞減)。
問遍歷所有的子序列,總操作次數最少是多少。

Analysis

相同元素可能會帶來重複計數,我們統一先認為相同的元素出現時,左邊的更大。

考慮暴力做法。注意到我們這裡 只有 +1 操作,所以可以直接貪心。
每次枚舉區間,設:
– M[l][r] 表示 [l, r] 區間最大的數的位置。
– L[l][r] 表示把 [l, r] 這個區間處理成遞增序列的最小代價。
– R[l][r] 表示把 [l, r] 這個區間處理成遞減序列的最小代價。

那麼我們枚舉所有的區間,統計所有 L[l][m] + R[m][r] 就是答案,可以預處理這些數組,複雜度 O(n2),可以過小數據。

考慮大數據,其實題目里已經瘋狂暗示你了要用單調棧(stack)。。。
回憶 POJ 2559. Largest Rectangle in a Histogram

我們發現之前是要處理出,以 h[i] 為最低點,左右兩邊分別可以延伸多遠。
這裡恰好是求,以 h[i] 為最高點,左右兩邊分別可以延伸多遠,假設就是 Dl[i] 和 Dr[i]。
這樣唯一不同的是,我們還需要一個累計代價數組 Sl[i] 和 Sr[i],分別表示以 h[i] 為最高點,往左和往右累計的代價。
因為最後答案就是:
$$\Sigma_{i=1}^n Dl[i] * Sr[i] + Dr[i] * Sl[i]$$

我們可以在維護單調棧的過程中,順路求 Sl 出 Sr。不放考察從左往右掃描求 Dl 的過程。
設當前掃描到位置 i,將要被彈出的棧頂元素為 sp,這個位置右邊一直到 i 這個區間現在都至少需要是 h[sp] 的高度才符合要求。
記這個代價為小寫的 sl,我們預處理部分和後可以 O(1) 的求出 sl。記新的棧頂元素的位置與剛才被我們彈出的棧頂元素的位置之間的距離為 sp – s.top(),
sl 需要被統計 sp – s.top() 次。最後加上這個區間本身的代價 Sl[sp]。

stack<int> s; s.push(0); REP_1(i, n) {
    Sl[i] = 0;
    while (h[i] > h[s.top()]) {
        int sp = s.top(); s.pop();
        Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
        Sl[i] += sl * (sp - s.top()) + Sl[sp];
    }
    Dl[i] = i - s.top();
    s.push(i);
}