前回(動的計画法(Dynamic Programming)演習 - るくすの日記 ~ Out_Of_Range ~)の続き。今回は該当するDiv2Hardのうち13問解きました。 [Div2](SRM354) 1000:UnsealTheSafe dp[i][j] := i-1番目にjを押すようなパスワードの総数 sum += dp[i - 1][keypad[ny][…

タイトルのまんまです。 TopCoder SRMの過去問から解法に「Dynamic Programming」が含まれている問題をレベルで昇順にソートして解いていきます。 該当するDiv2Medium全18問中15問解きました。(残り3問は、dpでふつう解かないだろうみたいな問題だったので別…

[問題] 2112 -- Optimal Milking牛とミルクマシーン(適当)が辺で接続されている。全ての牛をミルクマシーンに到着させたい。この時もっともたくさん歩く牛の距離を最小化せせよ。ただし、ミルクマシーンはm匹の牛しか処理できない。 [解法] WarshallFloyd + …

[問題文] 1949 -- ChoresN個の仕事がある。それぞれにかかる時間と、その仕事より必ず先に終わらせなければならない仕事k個の情報が与えられる。 仕事は並列で行うことができる。N個の仕事を終わらせるのにかかる時間を最小化せよ。 [解法] トポロジカルソー…