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] 为最高点,往左和往右累计的代价。
因为最后答案就是:

我们可以在维护单调栈的过程中,顺路求 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 .. ) ゆっくり読んでください ...