Educational DP Contest / DP まとめコンテスト Q - Flowers
解法
とりあえず、最終的に残る花は、かつ
を満たすので、LISっぽいことを考えてみます。
一番高さが高い(つまり右端)花の番号が
になるような並べ方の中での、美しさの総和の最大値
とします。
すると、次のような操作を、が小さい方から行えばよいことがわかります。
番目の花を見るとき、
(ただし、
)
となります。
区間についてのdpの最大値は、dpの配列をRMQで表現することによって、高速に計算することができます。
あとはこのDPを解けば、この問題の答えがわかります。
感想
LISっぽいな、ということはわかってたのですが、最大値を計算する方法がわからずずっと悩んでいました。ただたんにRMQを使うだけでよかったのですね…
思考の流れとしては、まずかつ
を満たすような列を作成するので、LISが絡んでいそう、と目星を付けます。一番基本的なLISは二分探索を利用するので、まずは二分探索を考えますが、dp配列の添え字を
ベースにすると、中身が常に単調増加になっているわけではないので、二分探索は使えなさそう、という考えに至ります。そこで、ある区間に対する最大値を求める方法もしくはデータ構造はなんだろう、と考えたときに、セグメント木を利用すればいい！となり、あとはそれを利用することで、この問題が解けました。
結果的には、RMQをただ貼り付けるだけなので、あんまりDPっぽくは感じませんでした…
