poj1947-第一道树形dp，哎，欲哭无泪

第一道树形dp，欲哭无泪。

不知道如何说，首先对树学习的不深，大学上课的时候这些东西考试内容很固定，学的时候又有点吃力，所以学的不是很深。其次对于dp，其实也就是计算里面的迭代，但是这个方面确实博大精深，我曾经也是浅尝则止，导致此题感觉越发困难。最后递归，这是我学习过程中，认为最不好理解的一个算法，很难想象，但是递归之美不是让你去想象，而是去分析，如何才能递归。。。

然而这道题目，这三方面的知识都用到了，必须欲哭无泪，看了好久，下不了手，还是硬着头皮去学习，去分析，写出自己的心得。

题目很好理解，就是一棵树，问问如何减去最少的边，得到一个含有p个节点的子树。。。

这题满足所谓的最优子问题，记忆化搜索等等，因此符合动态规划，不同的是，这个dp要在树上进行。

dp状态方程

dp[s][i]:记录s结点，要得到一棵j个节点的子树去掉的最少边数
考虑其儿子k
1）如果不去掉k子树，则
dp[s][i] = min(dp[s][j]+dp[k][i-j]) 0 <= j <= i

2）如果去掉k子树，则
dp[s][i] = dp[s][i]+1
总的为
dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) , dp[s][i]+1 )

到这里就可以放手去实现了。。。

代码：

#include <iostream>using namespace std;#define nMax 152#define inf 0x3fffffff/*dp[s][i]:记录s结点，要得到一棵j个节点的子树去掉的最少边数考虑其儿子k1）如果不去掉k子树，则dp[s][i] = min(dp[s][j]+dp[k][i-j])  0 <= j <= i2）如果去掉k子树，则dp[s][i] =  dp[s][i]+1总的为dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) ,  dp[s][i]+1 )*/int dp[nMax][nMax];int son[nMax], brother[nMax], root, n, p;bool fFather[nMax];void dfs(int s){int k ,tmp;for (int i = 0; i <= p; ++ i){dp[s][i] = inf;}dp[s][1] = 0;k = son[s];//printf("son[%d] = %d\n",s, k);while(k){dfs(k);for (int i = p; i >= 1; -- i){tmp = dp[s][i] + 1;for (int j = 1; j < i; ++ j){if (dp[k][i - j] + dp[s][j] < tmp){tmp = dp[k][i - j] + dp[s][j];}}dp[s][i] = tmp;//printf("dp[%d][%d] = %d\n",s,i,tmp);}k = brother[k];//printf("k = %d\n", k);}}int solve(){int ans;dfs(root);ans = dp[root][p];for (int i = 1; i <= n; ++ i)//若想自己独立为根，必须先与自己的父亲断绝关系。。所以除了根节点，其他的节点要想独立成根，成为最少去边数，必须先加上1{if (dp[i][p] + 1 <ans){ans = dp[i][p] + 1;}}return ans;}int main(){int s, t;while (scanf("%d%d", &n, &p) != EOF){memset(son, 0, sizeof(son));memset(fFather, false, sizeof(fFather));for (int i = 1; i < n; ++ i){scanf("%d%d", &s, &t);brother[t] = son[s];//记录同一个父亲下的上一个兄弟son[s] = t;//记录这个父亲的当前的儿子fFather[t] = true;//标示这个孩子有父亲，不是根}for (int i = 1; i <= n; ++ i){if (!fFather[i]){root = i;break;}}printf("%d\n", solve());}return 0;}