ぴょんぴょん川渡り(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書けるようになってきてうれしみ

まあ、まだまだなのだが