Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)

E. Skyline Photo

题意：

\(n\)个元素，每个元素有两个属性\(h\)和\(b\)，要求把这些元素划分为若干个子区间，每个子区间的价值为该区间内\(h\)最小的元素的\(b\)的值，求最优划分使得所有子区间价值之和最大

思路：

考虑一个\(O(n^2)\)的\(dp\)，\(dp[i]\)表示前\(i\)个元素的答案，那么\(dp[i] = max\{dp[j] + val(j + 1, i) | 1 <= j < i\}\)
尝试优化
设\(j\)为\(i\)左边第一个\(h\)小于\(i\)的下标，则\(dp[i] = max\{dp[k] | j <= k < i\} + b[i]\)
为什么不需要考虑\(k<j\)的情况？
假设\(x\)为\(j\)左边第一个\(h\)小于\(j\)的下标
则当\(x <= k < j\)时
\(dp[i] = max(max\{dp[k] | x <= k < j\} + b[j], max\{dp[k] | j <= k < i\} + b[i])\)
容易发现，前半部分就是\(dp[j]\)
所以\(dp[i] = max(dp[j], max\{dp[k] | j <= k < i\} + b[i])\)
用单调栈和线段树即可

#include<bits/stdc++.h>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 300010;
ll h[maxn], b[maxn], dp[maxn], mx[maxn << 2];
void pushUp(int rt){
    mx[rt] = max(mx[ls], mx[rs]);
}
void upd(int rt, int l, int r, int pos, ll c) {
    if(l == r){
        mx[rt] += c;
        return ;
    }
    int m = (l + r) >> 1;
    if(pos <= m) upd(ls, l, m, pos, c);
    else upd(rs, m + 1, r, pos, c);
    pushUp(rt);
}
ll ask(int rt, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr) return mx[rt];
    int m = (l + r) >> 1;
    ll ans = -1e18;
    if(ql <= m) ans = max(ans, ask(ls, l, m, ql, qr));
    if(qr > m) ans = max(ans, ask(rs, m + 1, r, ql, qr));
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    dp[1] = b[1];
    vector<int>sta;
    sta.push_back(1);
    upd(1, 1, n, 1, b[1]);
    for(int i = 2; i <= n; ++i) {
        while(!sta.empty() && h[sta.back()] > h[i]) sta.pop_back();
        int l = sta.empty() ? 0 : sta.back();
        if(!l)
            dp[i] = max(ask(1, 1, n, 1, i - 1), 0ll) + b[i];
        else
            dp[i] = max(ask(1, 1, n, l, i - 1) + b[i], dp[l]);
        upd(1, 1, n, i, dp[i]);
        sta.push_back(i);
    }
    cout << dp[n] << ‘\n‘;
    return 0;
}

Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)

原文：https://www.cnblogs.com/Zeronera/p/14719522.html