久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 方針 nが割と小さいのでDFSで間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…