全国統一プログラミング王決定戦本戦：E - Erasure

問題
解法
解答

問題

解法

dp(i, j) := 左から i 個のブロックまでの全てを爆破済みで，区間の右端が j になるような区間で爆破するときの通り数

と DP を立てる．j <= K のとき，爆破する区間を取ることが出来ないので dp(i, j) = dp(i, j + 1) となる．

そうでないとき，i + 1 個目のブロックを爆破するかどうかで場合分けする．

爆破するとき，j - K と i + 1 の大小関係で場合分けする．

j - K <= i + 1 のとき，どう区間をとっても i + 1 個目のブロックを爆破することになるので，2^(j - K) - 1 通り．ここで - 1 したのは何を区間を取らないと i + 1 個目のブロックを爆破しないことになってしまうから．

j - K > i + 1 のとき，区間の取り方によっては i + 1 個目のブロックを爆破しない場合が出てきてしまう．なので，区間の取り方のうち i + 1 個（＝ i + 1 個目のブロックを含む区間の取り方）は必ずどれか 1 つを採用しなければならないので 2^(i + 1) - 1 通り，そのほかの区間の取り方 j - K - (i + 1) 個に関しては採用するかどうかは完全に任意なので 2^(j - K - (i + 1)) 通り．この二つを掛け合わせたものが通り数になる．

場合分けして得られた通り数を dp(j, j + 1) とかけたものが dp(i, j) となる．遷移は O(1) で出来るので全体で O(N^2)．