区間を定義域とする動的計画法
-
どう求めるかに何パターンかある(組み合わせて使うこともある)
-
1: 縮める区間DP
- f(l, r)をf(l + 1, r)とf(l, r - 1)から求める
-
2: 中割りする区間DP
- f(l, r)をf(l, i)とf(i, r)から求める (l < i < r)
- O(N^3)になる
- 間に合わない時
- フェニック木などで範囲和を高速化する
-
3: 列から条件を満たす列を取り除く回数
- 図はPAST5Lのもの
- 条件を満たす3つの要素の並びを取り除くことができる
- 取り除く個数の最大化をしたい
- 1と2はやった上でそれに加えて3をやる
- 線で表現された区間が取り除かれた後、残った丸が条件を満たすパターン
- 図はPAST5Lのもの