# The Fourth Dimension Space

## POJ 1947 Rebuilding Roads 第一个树形DP

After solving this problem,I can't help admitting that DP is a world which fully fill with amazement，from the simple one dimension DP,to two dimension DP even to staue DP,tree DP,DP problem is just like a kaleidoscope. But the further reflection reveal that it is always the same because of the similar essence.in my eyes,every DP problem has a (mostly two dimension)table and a equation bewteen two states.If we can controll the table and the relationship between every states,we can conque the problem completely.
The following is my code ,according to the big fish foreverlin. #include<iostream> #include
<cmath> #include
<algorithm> #include
<vector> using namespace std; #define INF 999999999 #define MAX 151 vector
<int> hash[MAX]; int dp[MAX][MAX]; int n,p;  void dfs(int x)//x代表当前访问结点  { int i,j,k; int len=hash[x].size(); for(i=0;i<len;i++) dfs(hash[x][i]);  ////////////////////////////////////////////////////////////////////////// //后序遍历，从叶子往上逐层递推 if(x==1)    dp[x]=hash[x].size(); else dp[x]=hash[x].size()+1; for(k=0;k<len;k++)  { for(i=p-1;i>=1;i--)  { if(dp[x][i]!=INF)  { for(j=1;i+j<=p;j++)  { if(dp[hash[x][k]][j]!=INF) dp[x][i
+j]=min(dp[x][i+j],dp[x][i]+dp[hash[x][k]][j]-2); } } } } }    int main()  { scanf(
"%d%d",&n,&p); int i,j; int t1,t2; for(i=1;i<=n-1;i++)  { scanf(
"%d%d",&t1,&t2); hash[t1].push_back(t2); } for(i=1;i<=n;i++) for(j=1;j<=p;j++) dp[i][j]
=INF; dfs(
1); int ans=INF; for(i=1;i<=n;i++)  { if(dp[i][p]<ans) ans
=dp[i][p]; } printf(
"%d\n",ans); return 0;     }

posted on 2010-03-07 23:36 abilitytao 阅读(1136) 评论(0)  编辑 收藏 引用 