7K12 blog

猫でも分かるアルゴリズム解説

EDPC Q - Flowers

f:id:tkr987:20200507055133p:plain

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

in-place DPというやつらしい。

  • メイン条件 + index条件 → セグメントツリーにバラバラに入れる + RMQ (Range Max Query)

f:id:tkr987:20200507062034p:plain
逆の逆の操作は同値「背が高い∧indexが減少」を抜く⇔「背が低い∧indexが増加」を増やすと言い換える。前者より後者のほうが実装が楽になるため、後者の方法を考える。

 

背が低い順にというメイン条件があるため、まず背の順でソートする。ソートした花を昇順に見ていき「背が低い∧indexが増加」の答え(美しさ合計)をdpとするとdp[i] = a[i] + max( dp[0, i) )となる。dpが再帰的に定義されるので、dp[i]もmax( dp[0, i) )も「背が低い∧indexが増加」を満たす。普通のvectorではmax( dp[0, i) )の処理に  O(N) かかってしまうが、セグメントツリーにバラバラに入れていく実装で O(\log N)で処理できるようになる。セグメントツリーには点加算と区間最大値取得を実装する。