DP+樹。

設 dp[u][p] 表示以 u為root 切成 p點 最少切數。

可以知道 dp[u][1] = deg[u] (出度,u的子節點數目)。

dp[u][j+k] = min(dp[u][j+k], dp[u][j]+dp[v][k]-1)。

這邊我想了蠻久,終於發現他其實就是跟 01背包 很像,要 -1 是因為把 v 接回 u。

我的code

http://codepad.org/N38IHovv

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()