drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ シーケンシャルDP DP DP状態:ナップサック ナップサック 部分和 Yes/No判定問題 そのまま覚えたい典型問題 NoviSteps3Q 茶色diff AtCoder300点 ABC-C 数直線上のN点の問題 部分和問題・ナップサック問題とほとんど同じ DP で解ける！ 問題へのリンク 問題概要 数直線上で座標 0 から出発して、 回のジャンプをする。 回目のジャンプでは、正の方向に または の移動をする。 回のジャンプの末に座標 に到達することが可能かどうか判定せよ。 制約 解法 部分和問題とほとんど同様に解ける！ 部分和問題については次の記事を参照。 qiita.com この記事の「部分和問題」と同様の DP で解ける。次の配列を考えよう。 dp[i][x] ← 最初から 回のジャンプによって、座標 に到達することが可能かどうかを表すブール値 このとき、DP の更新式は次のように表せる。 x -… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F07%2F05%2F015244" title="AtCoder ABC 240 C - Jumping Takahashi (3Q, 茶色, 300 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2024-07-05 01:52:44 rich https://drken1215.hatenablog.com/entry/2024/07/05/015244 1.0 100%