読解が大変だけど、本質的には木 DP な問題
問題概要
本の棒を用いて、下図のようなモビールを作りたい。
入力としては、各棒 についての
- 左端から支点までの長さ
- 右端から支点までの長さ
- 左端からつながっている棒の index (重りの場合は 0)
- 右端からつながっている棒の index (重りの場合は 0)
が与えられる。重りの重さはすべて整数値でなければならない。考えられるモビールをすべて考えたときの、重りの重さの総和の最小値を求めよ。
制約
- (データセット数)
考えたこと
モビールは実際には木に過ぎない。木 DP と同じ発想が使える。
dp[i]
← モビール 以下のみを考えたときの、重りの重さの総和として考えられる最小値
とする。さて、dp[i]
を求めるとき
としよう。このとき、左側の重さの総和は の倍数となり、右側の重さの総和は の倍数となる。よって、てこの原理を考慮して
を満たす正の整数 の最小値を求めればよいということになる。具体的には、
としたとき、
とすればよいことがわかる。よって、
dp[i]
=
と求められた。このような DP を再帰的に実施すれば OK。なお、最初に根の位置を特定する必要がある。
コード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> P(N), Q(N), left(N), right(N); vector<int> par(N, -1); for (int i = 0; i < N; ++i) { cin >> P[i] >> Q[i] >> left[i] >> right[i]; --left[i], --right[i]; if (left[i] != -1) par[left[i]] = i; if (right[i] != -1) par[right[i]] = i; } // 根を特定 int root = -1; for (int v = 0; v < N; ++v) if (par[v] == -1) root = v; // DP auto rec = [&](auto self, int v) -> long long { // 葉の場合 if (v == -1) return 1; long long L = self(self, left[v]); long long R = self(self, right[v]); long long G = gcd(L*P[v], R*Q[v]); return L * R * (P[v] + Q[v]) / G; }; cout << rec(rec, root) << endl; }