Flowers [Educational DP Contest / DP まとめコンテスト Q]

https://atcoder.jp/contests/dp/tasks/dp_q

前提知識

• LIS（最長部分増加列）の派生
• インラインDP

解説

https://atcoder.jp/contests/dp/submissions/3973860

LISの派生系みたいな問題。
セグメントツリーでLISを解く方法を参考にして解く。
その方法を詳しく説明しよう。
　
考えやすいDPを出す。
dp[i][h] := i番目までの花を使った単調増加列で最後の高さがhである美しさの総和の最大値
この遷移を考えてみると、
dp[i+1][h] = dp[i][h] (h!=H[i])
dp[i+1][h] = max(dp[i][0], dp[i][1], ... , dp[i][h]) (h=H[i])
となる。
つまり、dp[i]の状態とdp[i+1]の状態はh=H[i]の1つしか変わらないということである。
そのため、大部分は領域を使い回せる。
なので、
dp[h] := 最後の高さがhである美しさの総和の最大値
とDPを定義しなおして、これを更新していくことでN個の花を見る。
具体的にはdp[i] = max(dp[i], max(dp[0], dp[1], ..., dp[H[i-1]]) + A[i]というのをN回行う。
これはdp[h]を区間maxのセグメントツリーで作っておけば実現できる。
このように更新箇所が少ないので、領域を使いまわしてDPするテクをインラインDPと言う。

int N, H[201010], A[201010];
SegTree<ll, 1 << 18> dp;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];
    rep(i, 0, N) cin >> A[i];
 
    rep(i, 0, N) {
        ll opt = dp.get(0, H[i]) + A[i];
        dp.update(H[i], max(dp[H[i]], opt));
    }
 
    cout << dp.get(0, 1<<18) << endl;
}