mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder bitDP 問題 問題概要 巡回セールスマン問題に辺のコストを加えたもの。 解法 巡回セールスマン問題ですね。bitDPで解きました。ただ今回の問題は、荷物をどれだけ持っているかで、1単位を移動するのにかかる時間が異なるので、それを前計算で、weight[mask] := mask集合を訪れた時に荷物の合計値を計算しておく。あとは、ddp[mask][i] := mask集合を巡って、iにいるときの最小コスト としてループで回して計算していく。 答えは、dp[(1 << (n + 1)) - 1][0]と、荷物を下すのにかかる時間(w1からw2の合計)である。荷物を下すのにかかる時間はどのような順番で街を… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F10%2F21%2F155306" title="yukicoder No.134 走れ！サブロー君 - srupのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-10-21 15:53:06 rich https://mmxsrup.hatenablog.com/entry/2016/10/21/155306 1.0 100%