まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!!
一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。
問題概要
0
と 1
のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。
今、文字列中の 個の連続する区間 (
番目の区間を
とします) が与えられます。これらの区間を用いて、0-1 文字列
のスコアは次のように計算されます。
- 各
について
- 文字列
の区間
の内部に
1
が一個でも存在するならば、スコアにを加算する
0-1 文字列のスコアとして考えられる最大値を求めてください。
制約
解法
もし がすべて非負であったならば、
=
111...1
が最適でしょう (その場合のスコアは となります)。
実際には が負値となることもありますので、その場合は区間内部はすべて
0
にしておきたいところです。しかしそうしますと、他の正値なスコアを取りこぼしてしまう可能性もあります。このように「全体のバランス」を考えないといけない場合は、DP で解決できる場合が多々あります。
さてこの問題は、結果的に DP 配列自体をセグメント木 (特に Starry Sky Tree) に載せて in-place に更新するような解法で解けます。in-place DP について特集した次の記事で詳しく解説しました。