競技プログラミング用 知識集積所
Q - Flowers
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
その花を右端とする場合の最大価値を記録していけばいいだけの動的計画法に見える。
しかし、左から順にデータを埋めていこうとしても、愚直に調べる方法ではTLE。
かといって、他に効率よく最大価値を調べる方法もない。
しかし、左から順にデータを埋めていこうとしても、愚直に調べる方法ではTLE。
かといって、他に効率よく最大価値を調べる方法もない。
そこで、自分より左にいる自分より高い花は結果に影響されないことから、DPの順番を変える。
つまり、左から順にではなく、低い花から順に最大価値を求めていくことにする。
つまり、左から順にではなく、低い花から順に最大価値を求めていくことにする。
そうすると、自分より高い花の位置には0が入っているので、単純に左側の記録の最大値+自分の価値で、記録すべき値を求めることができる。
これは、segment木（未作成）を用いれば愚直にやるより高速に処理できる。
これは、segment木（未作成）を用いれば愚直にやるより高速に処理できる。
低い順に処理するためには、最初にhの逆写像（未作成）を作るとよい。
hの制限は、よく見ると1以上N以下の花が1本ずつあるという制約である。
hの制限は、よく見ると1以上N以下の花が1本ずつあるという制約である。
