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);
}

Google Code Jam 2013 Round 3

Problem A. …..

Brief description:

。。。轉盤賭博問題。。一共有 37 個數字。。轉到某個數字後得到這個投注的 36 倍。。。(負和?
。。現在你發現賭場的這個裝置是有問題的。。既每次只會隨機停留在投注最少的數字上。。
你決定舉報之前。。先儘可能撈回本。。。於是你決定下一輪最後一個投注。。給定你當前的籌碼和目前的局面。。。
。。。問你此輪的最大的期望收益是多少。。)
ゆっくり読んでください …

Google Code Jam 2013 Round 2

Problem A. Ticket Swapping

Brief description:

… 給定一個直線形的地鐵站,一共 n 站,只能向一個方向移動。。每一站單站價格是從 n 開始每次減 1。
。。bug 是這個系統可以通過在站內交換車票來達到 cheat 的效果。。
。。給定 m 個請求 l, r, p 表示從 l 發出 p 個客流倒 r。
。。問整個系統最多會損失多少¥。。。
( n < = 1e9, m <= 1e3 .. ) ゆっくり読んでください …