[AtCoder] ABC087 C – Candies

Candies

https://beta.atcoder.jp/contests/abc087/tasks/arc090_a

動的計画法の問題ですが、使わなくても解けるようです。動的計画法の問題の中でも簡単な部類だと思います。

考え方

\( B[i][j]\) を マス \( (i, j) \) における所持しているアメの最大値とします。マスの移動は右か下しか行くことができないので、下に行くことができるのは移動のなかで一回だけになります。

したがって、

$B[0][j] = B[0][j – 1] + A[0][j]$

が成り立ちます。これは最初からずっと右方向に移動してアメを回収していくことを意味します。

\( B[1][j]\) については、次の式が成り立ちます。

$B[1][j] = A[1][j] + \max (B[1][j – 1],\ B[0][j])$

これは、マス \( (1, j) \) への行き方が左から来るのか、上から来るかの2通りだからです。したがって、\( B[1][N – 1]\) が解答になります。

ソースコード

感想

動的計画法はC問題でも使うことがあるので、色々なパターンに適応できるようになりたいですね。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする