tsutaj https://blog.hatena.ne.jp/tsutaj/ hogecoder https://tsutaj.hatenablog.com/ その他コンテスト グラフ 動的計画法 問題概要 問題原文 → Problem C2: Gold Mine - Chapter 2 | Facebook Hacker Cup - 2021 - Qualification Round 頂点の木があり、それぞれの頂点 には重み がついている。木から高々 個の辺素パスを取るとき、パスに含まれる重みの和の最大値を求めよ (ただしそれぞれの頂点の重みは一度のみ加算するものとする)。 ※元の問題は C1, C2 に分かれていますが、C1 では で固定です。この記事では C2 について解説しています。 解法 頂点 を根として、根付き木として考察します。動的計画法 (DP) で解くことができます。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftsutaj.hatenablog.com%2Fentry%2F2021%2F08%2F31%2F155631" title="FaceBook Hacker Cup 2021 Qualification Round C: Gold Mine - hogecoder" 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 2021-08-31 15:56:31 rich https://tsutaj.hatenablog.com/entry/2021/08/31/155631 1.0 100%