【每日一题】Tower of Hay 题解(单调队列优化dp)

Description

一堆数字，必须从左到右且全部取出，从下往上放，满足下层 $\geq$ 上层, 求所能得到的最高层。如下图为两层：
图片说明
样例解释：

3
1 2 3

第一层(最下面)放1 2，第二层放3，答案为2

Solution

瞎贪心肯定是不可取的，但是需要知道一个事实：在构造的过程中，在相同高度下，最底层的数字和越小，结果最优。
理性的感受一下就是：最底层的数字和越小，越能够将剩余的放到上面，从而使得最终高度越高。
给出一组数据

5
5 4 3 2 100

可能在分析的的时候出现 100 无处可放的情况，不妨从后往前(即从上往下放)，需要满足递增
即变成

5
100 2 3 4 5

令 $dp[i]$ 表示到了第 $i$ 个数字的时候，当前底层以第 $i$ 个数字结尾时，所能达到的最大高度。
我们用一个 $d[i]$ 记录此时最底层的数量。
那么肯定存在一个最优转移点 $j$ 满足

$sum[i] - sum[j] = d[i]$
$dp[i] = dp[j] + 1$

有限制条件 $sum[i] - sum[j] >= d[j]$
由结论：在相同高度下，最底层的数字和越小，结果最优，得知需要找到 $sum[i] >= d[j] + sum[j]$ 里找到最大的 $j$
对于 $d[j] + sum[j]$ 具有上界 $sum[i]$
维护一个递增的单调队列，每次找到最大的满足条件的 $j$ 即可。
时间复杂度 $O(n)$

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1000000007;
/*
相同高度下底层越小越好
*/
void solve() { 
    int n; cin >> n;
    vector<int> a(n + 1, 0), dp(n + 1, 0), d(n + 1, 0);
    vector<ll> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    reverse(a.begin() + 1, a.begin() + 1 + n);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    deque<int> q;
    int pos = 0;
    std::function <int(int)> cal = [&] (int id) -> int {
        return sum[id] + d[id];
    };
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && sum[i] >= cal(q.front())) {
            pos = q.front(); q.pop_front();
        }
        d[i] = sum[i] - sum[pos];
        dp[i] = dp[pos] + 1;
        while (!q.empty() && cal(i) <= cal(q.back())) {
            q.pop_back();
        }
        q.push_back(i);
    }
    cout << dp[n] << '\n';
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0);
    int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}