pkudp,pku 1947 Rebuilding Roads 树形DP~~

很简单的一道树形DP，把我搞得太纠结了。。。。
我也知道需要把子树的情况进行背包，不过不知道该怎样写，看了别人的代码，也能明白，就是自己那个时候怎么没想起来呢。。。
题意：给一个包含n个节点的树，然后让你找一颗节点数为p的子树，同时让你删掉最少数目的边把这个子树给孤立起来，问这个最少的边数。
思路：很容易想到要用到01背包，要把子树的情况进行背包。用dp[root][j]记录 以root为根的、节点数为j的子树的孤立起来需要删除的最少的边数。
状态方程为：dp[root][p]=min(dp[root][p], dp[u][k]+dp[root][p-k]-2);（其中u为root的一个孩子）
由于u与root之间的边连接了起来，所以dp[u][k]+dp[root][p-k] 多加了2次他们之间的边，所以要减去2；
含义是：我们把以 root 为根的节点的子树，把每一个分支作为背包的物品，决策就是每一个分支的选与不选，
而对于每一个分支的状态其实就是该问题的一个子问题，然后这样分割成 2 块后，我们会发现多砍了该节点与子节点的边两次，要减去之；
代码：
View Code 1 # include 2 # include 3 # define N 155 4 int n,p; 5 struct node{ 6 int from,to,next; 7 }edge[2*N]; 8 int head[N],tol,ans[N],dp[N][N]; 9 void add(int a,int b) 10 { 11 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++; 12 } 13 int min(int a,int b) 14 { 15 return a1;j--) 30 { 31 for(k=1;k

Tags:  roads pku树形dp pkudp

延伸阅读