最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。

問題概要

長さ $N$ の数列 $A$ が与えられる。数列 $A$ の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。

制約

$1 \le N \le 10^{5}$
$0 \le A_i \le 10^{5}$

考えたこと

最長増加部分列を求める方法にはいくつかあるが、インライン DP (セグ木上の DP) による方法が一つある (他の方法は蟻本に載っている)。

dp[ i ][ v ] := 最初の i 要素の中から、最後の値を v として、v がラストに来るような増加部分列の長さの最大値

として、

dp[ i + 1 ][ $A_{i}$ ] = $\max_{j \le A_{i}-1}$ (dp[ i ][ j ]) + 1

とする感じ。ここで添字 i の部分は配列をそのまま再利用することにすれば、毎回のステップで

dp[ $A_{i}$ ] = $\max_{j \le A_{i}-1}$ (dp[ j ]) + 1

という更新を行うことになる。この max を取る部分は、セグ木に乗せることで高速化ができる。

今回はさらに、増加部分列の総和も最大化する必要がある。これは (増加部分列の長さ, 増加部分列の総和) のペアを辞書順で最大化する問題と読み替えることができる。そうすると、dp の値をペアでもつように拡張して

dp[ v ] := 最初の i 要素の中から、最後の値を v として、v がラストに来るような増加部分列の (長さ, 総和) のペアの辞書順最大値

としてあげればよい。

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int SIZE_R;
    vector<Monoid> dat;
    
    SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, UNITY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update a, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get [a, b), a and b are 0-indexed */
    Monoid get(int a, int b) {
        Monoid vleft = UNITY, vright = UNITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }                                                                                                              
        return F(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            cout << (*this)[i];
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};


const int MAX = 110000;
const long long INF = 1LL<<60;

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    using pll = pair<long long, long long>;
    auto f = [](pll a, pll b){return max(a, b);};
    SegTree<pll> rmq(MAX, f, pll(-INF, -INF));
    rmq.update(0, pll(0, 0));
    for (int i = 0; i < N; ++i) {
        auto p = rmq.get(0, A[i]);
        rmq.update(A[i], pll(p.first + 1, p.second + A[i]));
    }
    pll res(0, -INF);
    for (int v = 0; v < MAX; ++v) {
        auto pi = rmq.get(v, v+1);
        if (pi.second < 0) continue;
        res = max(res, pi);
    }
    cout << res.second << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2941 LISum (RUPC 2019 day1-E)

問題概要

制約

考えたこと