題大意是：給你一棵節(jié)點為n的樹，問至少砍幾刀可以孤立出一棵節(jié)點為m的子樹。

解題思路：這題很容易想到狀態(tài)dp[i][j]表示以i節(jié)點為根，節(jié)點總數(shù)為j的子樹最少需要切幾刀。但是這個狀態(tài)方程確實很難想，dp[i][j+k]=min{dp[i][j]+dp[son[i]][k]-1，dp[i][j+k]};關鍵是為什么要減1，因為一開始dp[i][1]=直接子節(jié)點數(shù)，相當于i節(jié)點本身是一個孤立的狀態(tài)，而dp[i][j]是由dp[i][1]往上推過去的，就相當于i這棵子樹把son[i]這個子樹給切開了，所以合起來的時候要把這一刀減掉。

這個狀態(tài)轉移方程確實夠難想的。

轉載：http://blog.csdn.net/balloons2012/article/details/7844871

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 155; struct Edge {int to,next; }edge[maxn]; int n,m,cnt,pre[maxn],num[maxn],dp[maxn][maxn];void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].next = pre[u];pre[u] = cnt++; }void dfsDP(int u) {for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].to;dfsDP(v);for(int j = m; j >= 1; j--)for(int k = 0; j - k >= 0; k++)dp[u][j] = min(dp[u][j],dp[u][j-k] + dp[v][k] - 1);} }int main() {int u,v;while(scanf("%d%d",&n,&m)!=EOF){memset(pre,-1,sizeof(pre));memset(dp,0x1f,sizeof(dp));memset(num,0,sizeof(num));cnt = 0;for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);addedge(u,v);num[u]++;}for(int i = 1; i <= n; i++)dp[i][1] = num[i];dfsDP(1);int ans;for(int i = 1; i <= n; i++){if(i == 1) ans = dp[1][m];else ans = min(ans,dp[i][m]+1);}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1947(树形dp+背包问题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。