ぴょんぴょん川渡り(JOI2008-4)
(AtCoderのページ)https://joi2008ho.contest.atcoder.jp/tasks/joi2008ho_d
DPですね
どこからどこへ飛ぶかは最悪100通りなのですべて試しても間に合う
dp[i][j][k]:=k回1行飛ばしのジャンプをしてi列目、j番目の石にいる時の最小危険度
通常のジャンプの場合
i-1行目k番目の石からi行目j番目の石に飛ぶ場合
ll cost = (d[i][j] + d[i - 1][k]) * abs(x[i][j] - x[i - 1][k]); dp[i][j][l] = min(dp[i][j][l] , dp[i - 1][k][l] + cost);
一行飛ばしジャンプの場合
i-2行目k番目の石からi行目j番目の石に飛ぶ場合
ll cost = (d[i][j] + d[i - 2][k]) * abs(x[i][j] - x[i - 2][k]); dp[i][j][l] = min(dp[i][j][l] , dp[i - 2][k][l - 1] + cost);
こんな感じ
(僕のコード)https://joi2008ho.contest.atcoder.jp/submissions/1988036
DP書けるようになってきてうれしみ
まあ、まだまだなのだが