emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ 木上のナップサック 動的計画法(DP) 問題文 提出コード 解法 解説の通りこちらを参考にして通しました。 再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列と、使用しなかった際の最適解配列を返します。 今いる頂点をとします。子をとします。 1つめの子に対する再帰 引数で渡された配列をそのまま子の引数にします。 戻ってきた値について、 の処理は、それぞれの添え字について、で更新します。 についての処理は、今いる頂点と両方を使用するときは、コストがかかることに注意し、で更新します。 2つ目以降の子に対する再帰 について考えます。 をまず引数にして再帰します。 そして、先ほどとほぼ同様の処理、具体… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2020%2F02%2F21%2F192700" title="AOJ 2966 - G トレジャーハンター (Treasure Hunter) - ツバサの備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2020-02-21 19:27:00 rich https://emtubasa.hateblo.jp/entry/2020/02/21/192700 1.0 100%