drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ JOI JOI本選 JOI難易度7 AtCoder AOJ 数学(整数問題) グラフ 木 最大公約数 有理数 DP 木DP NoviSteps1D 読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (重りの場合は 0) 右端からつながっている棒の index (重りの場合は 0) が与えられる。重りの重さはすべて整数値でなければならない。考えられるモビールをすべて考えたときの、重りの重さの総和の最小値を求めよ。 制約 (データセット数) 考えたこと モビールは実際には木に過ぎない。木 DP と同じ発想が使える。 dp[i] ← モ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F01%2F04%2F031900" title="JOI 本選 2007 E - 最軽量のモビール (AOJ 0520) (1D, 難易度 7) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2021-01-04 03:19:00 rich https://drken1215.hatenablog.com/entry/2021/01/04/031900 1.0 100%