けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね！！！

0 と 1 のみからなる長さ $N$ の文字列を 0-1 文字列と呼ぶことにします。

今、文字列中の $M$ 個の連続する区間 ( $i$ 番目の区間を $\lbrack l_{i}, r_{i} \rbrack$ とします) が与えられます。これらの区間を用いて、0-1 文字列 $S$ のスコアは次のように計算されます。

各 $i = 1, 2, \dots, M$ について
文字列 $S$ の区間 $\lbrack l_{i}, r_{i} \rbrack$ の内部に 1 が一個でも存在するならば、スコアに $a_{i}$ を加算する

0-1 文字列のスコアとして考えられる最大値を求めてください。

もし $a_{i}$ がすべて非負であったならば、 $S$ = 111...1 が最適でしょう (その場合のスコアは $\sum_{i = 1}^{M} a_{i}$ となります)。

実際には $a_{i}$ が負値となることもありますので、その場合は区間内部はすべて 0 にしておきたいところです。しかしそうしますと、他の正値なスコアを取りこぼしてしまう可能性もあります。このように「全体のバランス」を考えないといけない場合は、DP で解決できる場合が多々あります。

さてこの問題は、結果的に DP 配列自体をセグメント木 (特に Starry Sky Tree) に載せて in-place に更新するような解法で解けます。in-place DP について特集した次の記事で詳しく解説しました。