[AtCoder] ABC 129 C – Typical Stairs
問題
方針
動的計画法
今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。
\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。また、\( i = a_j \ (1 \leq j \leq M)\) を満たす全ての \( i \) について、\( d_i = -1 \) とします。その他の \( i \) については、\( d_i = 0 \) と初期化します。
次に、遷移の仕方は、\( d_i \neq -1 \) を満たし、\( d_{i + 1} \neq -1 \) または、\( d_{i+2} \neq -1\) を満たすとき、それぞれ遷移できるので、
\[
\begin{eqnarray}
d_{i+1} &=& d_{i+1} + dp_{i}\\
d_{i+2} &=& d_{i+2} + dp_{i}
\end{eqnarray}
\]
となります。
コード
提出したコード
動的計画法
ll dp[N + 2]{}; dp[0] = 1; for (int i = 0; i < M; i++) { cin >> a[i]; dp[a[i]] = -1; } for (int i = 0; i < N; i++) { if (dp[i] == -1) continue; if (dp[i + 1] != -1) { dp[i + 1] += dp[i]; dp[i + 1] %= mod; } if (dp[i + 2] != -1) { dp[i + 2] += dp[i]; dp[i + 2] %= mod; }
ディスカッション
コメント一覧
まだ、コメントがありません