fc2ブログ



会津山スキー場の新企画

2009.09.07 22:50  パソコン甲子園 2009

パソコン甲子園2009予選 問題09 会津山スキー場の新企画

問題はこちら

典型的な動的計画法の問題です。

マス(y, x)にたどり着く場合の数は、以下のものの合計になります:
  • マス(y-1, x) (そこが移動可能なマスの場合)
  • マス(y-1, x-1) (そこが移動可能なマスの場合)
  • マス(y-1, x+1) (そこが移動可能なマスの場合)
  • マス(y-2, x) (そこがジャンプ台の場合)

ただし、 y が増えていく方向に(順番に)計算を行います。
例えば、マス(y, x)が移動可能な場所であれば、
マス(y+1, x)
マス(y+1, x-1)
マス(y+1, x+1)
にそれぞれ マス(y, x)の値を加算していきます(移動可能な場合のみ)。

スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ