樹形動的計画法の典型アルゴリズムと問題解説
二分リンゴの木 (Binary Apple Tree)
この問題は「樹上ナップサック」の典型例です。木の枝に重みが付いており、保持する枝の数を制限したときの最大価値を求めます。
状態定義:
dp[u][j] : 頂点 u を根とする部分木において、j 本の枝を残したときの最大価値。
遷移式:
dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + edge_weight)
ここで v は u の子、k は子 ...
10月20日 15:44 投稿