mmxsrup https://blog.hatena.ne.jp/mmxsrup/ srupのメモ帳 https://mmxsrup.hatenablog.com/ yukicoder メモ化再帰 dfs 問題 問題概要 省略 解法 メモ化再帰で解いた。サンプルで与えられている図のように辺を張り、dp[i] := i番目の商品が必要な数 とおき、自分の子で必要なものの数から、i番目に必要な個数を計算する形にした。商品nが必要な個数は1個なので、dp[n - 1] = 1となり、それを基底部としている。ほかの部分はu -> vとなっているとき、uの必要な個数は、(vの必要な個数)と(uからvを作るのに、必要な個数)の積でわかる。これをメモしながら、やっていけばいい。 ミス 図のグラフと逆向きのDAGではじめ書いたけど、TLE。治せなかった。 コード #include <iostream> #inc… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmmxsrup.hatenablog.com%2Fentry%2F2016%2F09%2F24%2F124158" title="yukicoder No.30 たこやき工場 - 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-09-24 12:41:58 rich https://mmxsrup.hatenablog.com/entry/2016/09/24/124158 1.0 100%