最軽量のモビール(07本選5)

N個の棒があり、そのそれぞれにひもがつながっている。一番上の棒をつるしているひもを除いては、ひもの下には棒かおもりがある。

角棒について、自分をつるしているひもより左の長さ、右の長さ、左につるしている棒の番号、右につるしている棒の番号(おもりなら0)が与えられる。

つり合いを取れるようにし、かつおもりを最軽量化した時の重りの重さの合計を求める問題。

一番上の棒から再帰的に下の棒を見ていき、つり合いがとれていなければつり合うようにし、より軽量化できるなら軽量化する。

計算量わからない。

非情に実装難であると感じたので難易度は8程度に感じられた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2325265#1