CF1484E_牛客博客

Solution

每次遇到这种比较复杂的问题的时候，可以先从比较直观的暴力方法去考虑再去思考如何优化。
比如这道题，我们比较容易的想到的是 $O(N ^ 2)$ 的dp转移。
定义：

$f_i$ : 到第 $i$ 个建筑物的最大美丽值。

$val(i, j)$ : $i$ 到 $j$ 之间最矮的建筑物的美丽值，即 $b_{k(min_{k = i} ^ {k = j} h_k)}$ 。

$f_i = max_{j = 1} ^ {j = i - 1} \{f_j + val(j + 1, i)\}$
为了降低复杂度，DP存在很多种优化方式，而这道题需要用到单调队列优化。

仔细观察，我们可以发现 $f_i$ 是单调递增的， $val(i, j)$ 是固定的。
利用单调栈维护单调递减的 $h$ 数组对应的下标，对于 $i$ , 我们可以找到左侧最近的 $k$ , 使得 $h_k < h_i$ ，此时 $f_i$ 有两种可能：

将 $[k + 1, i]$ 和 $k$ 放入到一张照片，此时答案为 $f_i = f_k$
将 $[j, i]$ 放入到一张照片, $f_i = max_{j = k + 1} ^ {i - 1}f_j + b_i$

O(NlogN)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll LNINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 3e5 + 5;

int n, h[N], b[N], l[N];
ll f[N];

#define ls (p << 1)
#define rs (ls | 1)
#define tm ((tl + tr) >> 1)

ll mx[N << 2];

void up(int p) {
    mx[p] = max(mx[ls], mx[rs]);
}

void modify(int p, int tl, int tr, int pos, ll v) {
    if (tl == tr) {
        mx[p] = v;
    } else {
        if (tm >= pos) modify(ls, tl, tm, pos, v);
        else modify(rs, tm + 1, tr, pos, v);
        up(p);
    }
}

ll query(int p, int tl, int tr, int l, int r) {
    if (r < l) {
        return 0;
    } else if (l <= tl && tr <= r) {
        return mx[p];
    } else {
        ll ans = LLONG_MIN;
        if (tm >= l) ans = max(ans, query(ls, tl, tm, l, r));
        if (tm < r) ans = max(ans, query(rs, tm + 1, tr, l, r));
        return ans;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && h[stk.back()] > h[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) l[i] = stk.back();
        stk.push_back(i);
    }
    memset(mx, sizeof(mx), 0xc0);
    f[0] = LNINF;
    modify(1, 0, n, 0, 0);
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[l[i]], query(1, 0, n, l[i], i - 1) + b[i]);
        modify(1, 0, n, i, f[i]);
    }
    cout << f[n] << '\n';

    return 0;
}

Code O(NlogN)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

int n, h[N], b[N], stk[N];
ll stk_v[N], f[N];
bool in_queue[N];
priority_queue<pair<ll, int>> pq;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    int top = 0;
    for (int i = 1; i <= n; i++) {
        ll now = f[i - 1];
        while (top > 0 && h[i] < h[stk[top]]) {
            now = max(now, stk_v[top]);
            in_queue[stk[top]] = false;
            top--;
        }
        stk[++top] = i;
        stk_v[top] = now;
        in_queue[i] = true;
        pq.push(make_pair(now + b[i], i));
        while (!in_queue[pq.top().second]) pq.pop();
        f[i] = pq.top().first;
    }
    cout << f[n] << '\n';

    return 0;
}

O(N)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ls (p << 1)
#define rs (ls | 1)
#define tm ((tl + tr) >> 1)
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LNINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> h(n), b(n);
    for (auto &i : h) cin >> i;
    for (auto &i : b) cin >> i;
    vector<ll> f(n);
    stack<int> stk;
    stack<ll> stkdp, stkmax;
    for (int i = 0; i < n; i++) {
        ll mx = i == 0 ? 0 : f[i - 1];
        while (!stk.empty() && h[stk.top()] > h[i]) {
            mx = max(mx, stkdp.top());
            stk.pop();
            stkdp.pop();
            stkmax.pop();
        }
        stkdp.push(mx);
        if (stkmax.empty()) {
            stkmax.push(mx + b[i]);
        } else {
            stkmax.push(max(stkmax.top(), mx + b[i]));
        }
        f[i] = stkmax.top();
        stk.push(i);
    }
    cout << f[n - 1] << '\n';   

    return 0;
}