ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト W - Intervals

動的計画法(DP) Segment Tree(セグ木)

問題
 提出コード

解法

$dp[i] = i$ 文字目を"1"にした場合に、 $[1,i]$ で得られる得点の最大値
を考えます。
すると、
$i$ が間に含まれているものを除いた区間達について計算した場合の、 $[1,i-1]$ で得られる得点の最大値に、 $i$ が間に含まれている区間の得点の総和が、 $dp[i]$ の値になります。
これを上手く計算するには、

$dp[x] = max(dp[y]) (y \lt x)$ を計算する
$x = r_{i}$ を満たす全ての $l_{i},r_{i},a_{i}$ について、 $dp[z] (l_{i} \leqq z \leqq r_{i})$ に $a_{i}$ を加算する

という操作を、 $x$ が小さい方から順番に繰り返していけば良いです。
このようにすることで、それぞれの区間が重複して加算されるのを防ぐことができます。
答えは、 $dp[i]$ の中で最大のものを計算すればよいです。

感想

区間の重複加算を防ぐ方法を思いつくのに時間がかかりました…セグ木は便利ですね！