日経コン 2019 E - Erasure (700)
解法
dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた )
として, i 開始の区間を考える.
半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1.
新しく [0,x) から [0,j) ( x < j ) まで消す場合
[ i, j ) は必ず選ばなければならず, (よって j - i >= K+1 )
残りの [ i, i+K+1 ), ..., [ i, j-1 ) の j-i-K-1 は自由に決められるので
dp[ i+1 ][ j ] += ( sum _ { i <= x < j } dp[ i ][ x ] ) * 2j-i-K-1
一方, dp[ i ][ j ] から dp[ i+1 ][ j ] に遷移する場合は
i から始まる区間が j を超えてしまう場合( j < i+K+1 )は
dp[ i+1 ][ j ] += dp[ i ][ j ]
超えない場合は [ i, i+K+1 ), ... , [ i, j ) を自由に選べるので
dp[ i+1 ][ j ] += dp[ i ][ j ] * 2j-i-K
これを単に累積和で処理してやればいい.
メモ
簡単なはずなんだけどこんがらがってしまった..