POJ 3176 Cow Bowling
蟻本章末問題
問題概要
- ボーリングのピンが並んでる
- 一番前のピンを倒す
- その後ろのピンのうち左右どちらかのピンを倒すことができる
- さらに、その後ろのピンのうち左右どちらかのピンを倒すことができる
- 以上の作業を繰り返し一番後ろのピンまで倒す
- ピンには点数がついていて、倒すピンの点数の合計を最大化する
解法
- 動的計画法
- L[i][j] := 前からi番目, 向かって右からj番目のピンの点数
- dp[i][j] := 前からi番目, 向かって右からj番目のピンを倒し、一番後ろまで最適なピンを倒した時に得られる得点
- dp[i][j] := L[i][j] + max(dp[i+1][j], dp[i+1][j+1])
