会津山スキー場の新企画
2009.09.07 22:50 パソコン甲子園 2009
パソコン甲子園2009予選 問題09 会津山スキー場の新企画
典型的な動的計画法の問題です。
マス(y, x)にたどり着く場合の数は、以下のものの合計になります:
ただし、 y が増えていく方向に(順番に)計算を行います。
例えば、マス(y, x)が移動可能な場所であれば、
マス(y+1, x)
マス(y+1, x-1)
マス(y+1, x+1)
にそれぞれ マス(y, x)の値を加算していきます(移動可能な場合のみ)。
問題はこちら。
典型的な動的計画法の問題です。
マス(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) | ↑ページトップ |