CODE FESTIVAL 2018 qual A : C - 半分

問題
解法
解答

問題

解法

「dp(i, j, f) := i 番目までで j 回操作するときの通り数（f := 今までの要素を 0 にしたかどうか）」で DP をする．f が true のとき，操作の回数が余ったとしても，どこか 0 である要素で余った回数を消費すれば良いので，これによって重複を生まない DP 漸化式になる．

コンテスト中では「dp(i, j) := i 番目までで j 回操作するときの通り数」と考えていて，重複をどうやったら処理できるか悩んでいた．