読者です 読者をやめる 読者になる 読者になる

olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

ぴょんぴょん川渡り(08本選4)

N行に石があり、それぞれの行にある石の数と、位置と滑りやすさが決まっている。

向こう岸まで跳んで行った時の最小の危険度を求める問題。

なお、一行飛びジャンプはM回までできる。

dp[i行目までで][j回までの一行飛びジャンプを使い][i行目のk個目の石]にいるときの危険度の最小値をもって配るDPを回す。

計算量はO(NM)(定数倍が大きいけど)

難易度は6程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325302#1