Yukicoder 777 再帰的ケーキ
たまに目にする2次元LISなやつです。
まずシーケンスa[i]に対して、a[i_1] < a[i_2] < ... < a[i_k] となるような部分列の長さはLIS等の典型アルゴリズムで簡単に求められます。ここで、更に別のシーケンス b[i] も追加してb[i_1] < b[i_2] < ... < b[i_k] となるようにする、というお話です。
これは典型手段として下記のようにやるみたいです。
- b[i] を座標圧縮し、bx[i] (0<= bx[i] <= n-1) とする。(後にこの要素をインデックスとするRMQを用いるため)
- (a[i], bx[i]) という要素の列をa[i] 昇順、bx[i] 降順でソートする(これをすることにより、a[i] = a[i + 1] の場合のめんどくさいコーナーケースがなくなります。実験するとすぐわかります)
- 各(a[i], bx[i]) に対して、初期値0の数列dp[i] に対するRMQを用いて、[0, bx[i]) のdpmax を計算し、 d[i] = max(d[i], dpmax + 1) と更新する。
- d[i] には最後の要素がbx[i]であるような最大の部分列の長さが入っている
これは要はDP＋セグメント木による高速化を行っています。本来の遷移式は下記のとおりです。
dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + 1
単純に遷移を書くとO(N^2)ですが、maxはSegmentTreeでやることでO(N log(N))まで計算量が落ちています。
Yukicoderの方ではちょっとだけひねってあってあるケーキを追加する場合に1増えるのではなく、c[i]増えるという式になっています。ただ遷移式自体はほぼ変わらず以下のとおりです。
dp[i番目まで処理][最後のbx] = max{dp[i-1][j] | j = 0..bx-1} + c[i]
こうすることにより、答えは max{dp[n][j] | j = 0...n-1} となります。計算量はO(N log(N))。
